Rotate Array by K places | Union, Intersection of Sorted Arrays | Move Zeros to End | Arrays Part-2

Main ideas / lessons

• The video is a walkthrough of multiple Array DSA problems, emphasizing an interview-friendly workflow:
  1. Start with Brute Force (if applicable)
  2. Then move to Better
  3. Finally provide Optimal
• Always explain time and space complexity clearly, including the difference between:
  • Total space used by the given input structure
  • vs extra/auxiliary space
• Core techniques repeatedly used:
  • In-place array manipulation (to minimize extra space)
  • Modulo reasoning for large rotation counts
  • Two-pointer / sweep-line on sorted arrays (for union/intersection)
  • Swap-based partitioning for moving zeros
  • Reversals to rotate efficiently without extra arrays

---

Problem 1: Rotate array left by 1 position (in-place)

Concepts

• Rotating left by 1 means:
  • The first element moves to the end
  • Every other element shifts left by 1 index

Method (in-place, no extra array)

• Use a step-by-step shifting idea:
  • Temporarily save the last element (or the overwritten value) conceptually.
  • Shift elements one position left inside the same array.
  • Place the saved temporary value into the last index.
• Implementation intuition described:
  • Consider moving arr[i] to arr[i-1] for i = 1..n-1
  • Then set arr[n-1] to the saved first/last displaced value (as described in the walkthrough).

Complexity

• Time: O(n) (single pass)
• Extra space: O(1) auxiliary
• Interview note on space:
  • The array itself counts as “space used,” but extra/auxiliary is what we track—here it’s constant.

Follow-up extension

• Rotate left by d positions instead of 1.

---

Problem 1 (Follow-up): Rotate array left by d positions

Key concept: reduce large d using modulo

• Rotating by n returns the array to the same state.
• Therefore use:
  • d = d % n
• This works even when d is very large.

---

Brute-force approach (with temporary storage of first d elements)

Steps (as presented)

1. Step 1: Store first d elements in a temporary list/array
   • Loop i = 0 .. d-1 and push arr[i].
2. Step 2: Shift the remaining elements left by d
   • Displacement described as:
     • element at index i goes to index i - d
3. Step 3: Put the stored temporary d elements into the last d positions
   • Fill from index n-d to n-1 using the temporary array.

Complexity

• Time: O(n)
• Extra space: O(d) (temporary)

---

Optimal approach (reversal algorithm, still in-place)

Observation

• Rotation by d can be achieved using three reversals.

Steps (3 reversals)

1. Reverse the first d elements: reverse(arr, 0, d-1)
2. Reverse the remaining n-d elements: reverse(arr, d, n-1)
3. Reverse the entire array: reverse(arr, 0, n-1)

Complexity

• Time: O(n) (three linear reversals)
• Extra space: O(1) (in-place)

Note

• Mentioned that Java/C++ may have built-in reverse; otherwise write a manual reverse helper.

Extra interview follow-up

• If asked to rotate right by d, adapt the logic (exercise/task for viewers).

---

Problem 2: Move all zeros to the end

Problem idea

• Given an array with integers and zeros:
  • Keep non-zero order relative to the approach used
  • Move all zeros to the end

---

Brute-force approach (temporary list of non-zeros)

Steps

1. Scan array and store all non-zero elements into temp.
2. Overwrite the front of the original array with elements from temp.
3. Fill the remaining positions with zeros.

Complexity

• Time: O(n)
• Extra space: O(x) where x = number of non-zeros (worst case O(n))

---

Optimal approach (two-pointer with swapping)

Core two-pointer idea

• Maintain:
  • J = index of the first zero position (target position for next non-zero)
  • I = current scan index
• For each index I:
  • If arr[I] != 0, swap it with arr[J], then increment J
  • If arr[I] == 0, just increment I

Interview-stated steps

1. Step 1: Find the first zero position:
   • Initialize J = -1, scan until you find arr[J] == 0
   • If no zero exists, stop.
2. Step 2: Start scanning from I = J+1 to end:
   • When a non-zero is found at I, swap arr[I] and arr[J], then J++

Complexity

• Time: O(n)
• Extra space: O(1) auxiliary

---

Problem 3: Linear search

Concept

• Find the first occurrence of a target in an array using sequential scan.
• If not found, return -1.

Method (standard)

• Iterate i = 0..n-1:
  • If arr[i] == target, return i
• After loop, return -1

Complexity

• Time: O(n)
• Extra space: O(1)

---

Problem 4: Union of two sorted arrays (unique elements, sorted output)

Union definition (as taught)

• Combine both arrays’ elements but remove duplicates
• Output should be sorted

---

Brute-force approach (set)

Steps

1. Create an ordered set (e.g., set in C++).
2. Insert all elements from the first array, then all from the second array.
3. Convert the set into the output union list/array by iterating the set.

Complexity (as stated)

• Time: depends on set operations; worst-case described as O(n1 log n + n2 log n) (set size varies)

• Extra space: O(n1 + n2) in worst case

Note: explicitly cautioned against unordered sets because ordering matters.

---

Optimal approach (two pointers, sorted merge with de-dup)

Steps (two-pointer union construction)

• Maintain:
  • pointer i in array A
  • pointer j in array B
• Maintain an output list ans
• Loop while i < n1 and j < n2:
  • Choose the smaller of A[i] and B[j] as the next union candidate
  • Before appending, compare with ans.back() to avoid duplicates
  • Advance the pointer(s) that contributed to the chosen value:
    • If values are equal, advance both pointers
• After one array ends:
  • Append remaining elements from the other array, again avoiding duplicates vs ans.back()

Complexity

• Time: O(n1 + n2)
• Extra space: O(n1 + n2) for the returned answer (not for computation beyond output)

---

Problem 5: Intersection of two sorted arrays

Intersection definition (as taught)

• Elements present in both arrays
• Duplicates handling:
  • The explanation indicates taking matches respecting “visited” usage in brute force
  • In general interview terms, the optimal two-pointer approach naturally handles duplicates based on alignment in sorted order

---

Brute-force approach (visited tracking)

Steps

• Create visited for elements of one array (e.g., B) to mark used indices.
• For each element A[i]:
  • Scan through B with index j to find B[j] == A[i] that is not visited
  • If found and unvisited:
    • add to intersection answer
    • mark visited[j] = true
    • break to move to next A[i]
  • Optimization noted:
    • If B[j] > A[i] in a sorted array, break inner loop early (no further matches possible)

Complexity (as stated)

• Time: O(n1 * n2) worst case
• Extra space: O(n2) for visited (or similarly if reversed)

---

Optimal approach (two pointers)

Steps

• Maintain pointers:
  • i over A
  • j over B
• While i < n1 and j < n2:
  • If A[i] < B[j]: increment i
  • If A[i] > B[j]: increment j
  • If A[i] == B[j]:
    • append that value to intersection answer
    • increment both i and j

Complexity

• Time: O(n1 + n2) (each pointer advances monotonically)
• Extra space: O(1) auxiliary (excluding returned answer)

---

Speakers / sources featured

• Strials A2Z DSA course / Instructor — main narrator/teacher explaining all solutions
• YouTube channel “Strials A2Z DSA” — referenced as the course source