Notes on Left and Right Array Rotations, Zero Movements, Linear Search, and Array Unions/Intersections

Introduction

• This video is part of the Strivers A to Z DSA course.
• Course consists of 456 modules and over 400 problems.
• Aim: To help clear DS algorithms in interviews worldwide.

Left Rotate an Array by One Place

Problem Explanation

• Given an array, perform a left rotation by one place.
• Example: 1, 2, 3, 4, 5 becomes 2, 3, 4, 5, 1 after rotation.

Approaches

1. Brute Force: Use an additional array to store the rotated elements (not required for this problem).
2. Optimal Approach:
   • Use a temporary variable to store the first element.
   • Shift all other elements one index to the left.
   • Assign the temporary variable to the last index.

Implementation Steps

• Store the first element in a temporary variable.
• Loop through the array from index 1 to n-1, shifting each element left.
• Place the temporary variable at the end of the array.

Complexity Analysis

• Time Complexity: O(n) (single pass through the array).
• Space Complexity: O(1) (in-place operation).

Left Rotate an Array by D Places

Problem Explanation

• Rotate the array left by D places, where D can be any integer.

Modular Approach

• Use D % n (where n is the array size) to handle cases where D is greater than n.

Brute Force Approach

1. Store the first D elements in a temporary array.
2. Shift remaining elements left.
3. Place elements from the temporary array at the end.

Optimal Approach

• Reverse the first D elements.
• Reverse the remaining elements.
• Reverse the entire array.

Complexity Analysis

• Time Complexity: O(n) (three passes through the array).
• Space Complexity: O(1) (in-place operation).

Moving Zeros to the End

Problem Explanation

• Move all zeros in an array to the end while maintaining the order of non-zero elements.

Brute Force Approach

1. Create a temporary array to store non-zero elements.
2. Fill the original array with non-zero elements.
3. Fill remaining positions with zeros.

Optimal Approach

• Use a two-pointer technique to swap non-zero elements with zeros as you iterate through the array.

Complexity Analysis

• Time Complexity: O(n).
• Space Complexity: O(1).

Linear Search

Problem Explanation

• Find the first occurrence of a number in an array.

Approach

• Iterate through the array, checking if the current element matches the target number.
• Return the index if found, otherwise return -1.

Complexity Analysis

• Time Complexity: O(n).
• Space Complexity: O(1).

Union of Two Sorted Arrays

Problem Explanation

• Return the union of two sorted arrays without duplicates.

Brute Force Approach

1. Use a set to store unique elements from both arrays.
2. Convert the set back to a list for the result.

Optimal Approach

• Utilize two pointers to traverse both arrays:
  • If elements are equal, add to the result.
  • If one is smaller, move its pointer forward.

Complexity Analysis

• Time Complexity: O(n1+n2).
• Space Complexity: O(n1+n2) for the result.

Intersection of Two Sorted Arrays

Problem Explanation

• Return elements present in both arrays.

Optimal Approach

• Use a two-pointer technique to find common elements:
  • If elements are equal, add to the result and move both pointers.
  • If one is smaller, move that pointer forward.

Complexity Analysis

• Time Complexity: O(n1+n2).
• Space Complexity: O(n) for the result array.

Conclusion

• Recap of the problems discussed: left rotation, moving zeros, linear search, union, and intersection of arrays.
• Encourage viewers to practice the assignments given.