Array Rotations, Rearrangements, and Set Operations (Union & Intersection)

This chapter covers essential array manipulation techniques, starting with single and multi-place rotations, moving zeros to the end, and performing linear searches. It also explores set operations—specifically Union and Intersection—on sorted arrays. By transitioning from intuitive brute-force methods to highly optimized two-pointer and reversal algorithms, these notes build a robust foundation for solving complex array problems in technical interviews.

1. Left Rotate an Array by One Place

Left rotating an array by one place means shifting every element one position to the left, with the first element moving to the very end of the array.

Real-Life Analogy

Think of a queue of people waiting in a line. If the person at the front of the line is sent to the very back, everyone else steps forward by exactly one position.

Step-by-Step Evolution

To perform this rotation in-place without using an auxiliary array:

1. Store the first element (arr[0]) in a temporary variable temp.
2. Shift all remaining elements from index 1 to N-1 one position to the left (arr[i-1] = arr[i]).
3. Place the value stored in temp at the last index (arr[N-1]).

Implementation (C++)

#include <iostream>
using namespace std;

void leftRotateByOne(int arr[], int n) {
    int temp = arr[0];
    for (int i = 1; i < n; i++) {
        arr[i - 1] = arr[i];
    }
    arr[n - 1] = temp;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ because we iterate through the array of size $N$ exactly once to shift the elements.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space because the modification is done in-place.

  Note: If an interviewer asks for the space complexity of the algorithm, it is $\mathcal{O}(N)$ because it operates on an array of size $N$. However, the extra (auxiliary) space used is $\mathcal{O}(1)$. Always clarify this distinction in interviews.

2. Left Rotate an Array by D Places: The Brute Force Approach

When rotating an array by $D$ places, we shift the first $D$ elements to the end of the array, moving the rest of the elements forward.

Crucial Mathematical Observation

If the size of the array is $N$, rotating it $N$ times results in the original array. Therefore, rotating by $N, 2N, 3N$ places does not change the array. To handle cases where the number of rotations $D$ is greater than or equal to $N$, we simplify $D$ using the modulo operator:

The Brute Force Algorithm

1. Create a temporary array temp of size $D$ and copy the first $D$ elements into it.
2. Shift the remaining $N-D$ elements from the back to the front of the array.
3. Copy the elements from temp back into the last $D$ positions of the original array.

Mathematical Index Mapping

• Shifting: Elements starting from index $D$ up to $N-1$ are moved to index $i - D$.

• Copying Back: The last $D$ positions start at index $N - D$. For any index $i$ from $N - D$ to $N - 1$, the corresponding element in temp is at index $i - (N - D)$.

Implementation (C++)

#include <iostream>
#include <vector>
using namespace std;

void leftRotateBrute(int arr[], int n, int d) {
    d = d % n; // Handle cases where d >= n
    vector<int> temp(d);
    
    // Step 1: Store first d elements
    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    
    // Step 2: Shift remaining elements
    for (int i = d; i < n; i++) {
        arr[i - d] = arr[i];
    }
    
    // Step 3: Copy temp back to the end
    for (int i = n - d; i < n; i++) {
        arr[i] = temp[i - (n - d)];
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(D)$ [storing] + $\mathcal{O}(N-D)$ [shifting] + $\mathcal{O}(D)$ [copying back] = $\mathcal{O}(N + D)$ time.
• Space Complexity: $\mathcal{O}(D)$ auxiliary space because we store $D$ elements in the temporary array.

3. Left Rotate an Array by D Places: The Optimal Reversal Algorithm

To optimize the space complexity of the $D$-place rotation to $\mathcal{O}(1)$ auxiliary space, we can use a reversal algorithm.

The Reversal Mental Model

Suppose we want to left-rotate [1, 2, 3, 4, 5, 6, 7] by $D = 3$. We split the array into two logical parts:

• Part 1 (First $D$ elements): [1, 2, 3]
• Part 2 (Remaining $N-D$ elements): [4, 5, 6, 7]

The optimal algorithm performs three simple reversal steps:

1. Reverse Part 1: [1, 2, 3] $\rightarrow$ [3, 2, 1]
2. Reverse Part 2: [4, 5, 6, 7] $\rightarrow$ [7, 6, 5, 4]
3. Reverse the entire array: [3, 2, 1, 7, 6, 5, 4] $\rightarrow$ [4, 5, 6, 7, 1, 2, 3]

Implementation (C++)

#include <iostream>
using namespace std;

// Helper function to reverse array elements in-place
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

void leftRotateOptimal(int arr[], int n, int d) {
    d = d % n;
    reverseArray(arr, 0, d - 1);
    reverseArray(arr, d, n - 1);
    reverseArray(arr, 0, n - 1);
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(D)$ [first reverse] + $\mathcal{O}(N-D)$ [second reverse] + $\mathcal{O}(N)$ [full reverse] = $\mathcal{O}(2N) \approx \mathcal{O}(N)$ time.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space because all reversals are performed in-place.

4. Right Rotate an Array by D Places (Follow-Up Assignment)

Right rotating an array by $D$ places shifts elements to the right, with the last $D$ elements wrapping around to the front.

The Reversal Algorithm for Right Rotation

To right-rotate an array by $D$ places, we split the array into:

• Part 1 (First $N-D$ elements): [1, 2, 3, 4]
• Part 2 (Last $D$ elements): [5, 6, 7]

The steps are:

1. Reverse Part 1: [1, 2, 3, 4] $\rightarrow$ [4, 3, 2, 1]
2. Reverse Part 2: [5, 6, 7] $\rightarrow$ [7, 6, 5]
3. Reverse the entire array: [4, 3, 2, 1, 7, 6, 5] $\rightarrow$ [5, 6, 7, 1, 2, 3, 4]

Implementation (C++)

void rightRotate(int arr[], int n, int d) {
    d = d % n;
    reverseArray(arr, 0, n - d - 1);
    reverseArray(arr, n - d, n - 1);
    reverseArray(arr, 0, n - 1);
}

5. Move Zeros to the End: Brute Force Approach

The goal is to move all zeros in an array to the end while preserving the relative order of the non-zero elements.

The Brute Force Algorithm

1. Iterate through the array and copy all non-zero elements into a temporary array temp.
2. Copy the elements from temp back to the front of the original array.
3. Fill all remaining positions in the original array with 0.

Implementation (C++)

#include <iostream>
#include <vector>
using namespace std;

void moveZerosBrute(int arr[], int n) {
    vector<int> temp;
    
    // Step 1: Collect non-zero elements
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            temp.push_back(arr[i]);
        }
    }
    
    int nz = temp.size();
    
    // Step 2: Copy non-zero elements back
    for (int i = 0; i < nz; i++) {
        arr[i] = temp[i];
    }
    
    // Step 3: Fill the rest with zeros
    for (int i = nz; i < n; i++) {
        arr[i] = 0;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ [finding non-zeros] + $\mathcal{O}(X)$ [copying back] + $\mathcal{O}(N-X)$ [filling zeros] = $\mathcal{O}(2N) \approx \mathcal{O}(N)$ time, where $X$ is the number of non-zero elements.
• Space Complexity: $\mathcal{O}(N)$ auxiliary space in the worst case (when there are no zeros in the array, requiring temp to store all $N$ elements).

6. Move Zeros to the End: Optimal Two-Pointer Approach

To solve this problem in-place with $\mathcal{O}(1)$ auxiliary space, we use a two-pointer approach.

The Two-Pointer Mental Model

We use two pointers, j and i:

• j always points to the first available zero element.
• i is an explorer pointer that scans the array for non-zero elements to swap with j.

Step-by-Step Evolution

1. Find the first zero in the array and place pointer j there. If there are no zeros, the array is already in its final state; return early.
2. Start pointer i at j + 1.
3. If arr[i] is non-zero, swap arr[i] with arr[j], and increment j to point to the next zero.
4. If arr[i] is zero, do nothing and continue scanning with i.

Implementation (C++)

#include <iostream>
#include <algorithm>
using namespace std;

void moveZerosOptimal(int arr[], int n) {
    int j = -1;
    
    // Step 1: Find the first zero element
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            j = i;
            break;
        }
    }
    
    // If there are no zeros, no swaps are needed
    if (j == -1) return;
    
    // Step 2: Swap non-zeros with the zero at index j
    for (int i = j + 1; i < n; i++) {
        if (arr[i] != 0) {
            swap(arr[i], arr[j]);
            j++;
        }
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ because we make a single pass to find the first zero, followed by another pass to swap elements.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space because the swaps are performed in-place.

7. Linear Search: The Fundamental Iterative Search

Linear search is a straightforward search algorithm that checks each element of an array sequentially until a match is found or the entire array has been searched.

Implementation (C++)

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int num) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == num) {
            return i; // Return the index of the first occurrence
        }
    }
    return -1; // Return -1 if the element is not found
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ in the worst case (when the element is at the very end of the array or not present at all).
• Space Complexity: $\mathcal{O}(1)$ auxiliary space.

8. Union of Two Sorted Arrays: Brute Force Set-Based Approach

The union of two arrays contains all unique elements from both arrays, sorted in ascending order.

The Brute Force Algorithm

Since we need unique, sorted elements, we can use an ordered std::set in C++. An ordered set automatically prevents duplicate entries and keeps its elements sorted.

1. Insert all elements of the first array into the set.
2. Insert all elements of the second array into the set.
3. Copy the elements from the set into a result vector.

Implementation (C++)

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<int> unionBrute(int arr1[], int n1, int arr2[], int n2) {
    set<int> s;
    
    // Insert elements from the first array
    for (int i = 0; i < n1; i++) {
        s.insert(arr1[i]);
    }
    
    // Insert elements from the second array
    for (int i = 0; i < n2; i++) {
        s.insert(arr2[i]);
    }
    
    // Copy elements from the set to the result vector
    vector<int> unionArr;
    for (auto it : s) {
        unionArr.push_back(it);
    }
    
    return unionArr;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N_1 \log M + N_2 \log M)$ to insert elements into the set, where $M$ is the total number of unique elements ($M \le N_1 + N_2$). Copying the elements back takes $\mathcal{O}(N_1 + N_2)$ time.
• Space Complexity: $\mathcal{O}(N_1 + N_2)$ auxiliary space in the worst case to store the unique elements in the set.

9. Union of Two Sorted Arrays: Optimal Two-Pointer Approach

We can optimize the union operation to run in linear time and $\mathcal{O}(1)$ auxiliary space by taking advantage of the fact that both input arrays are already sorted.

The Two-Pointer Mental Model

We place a pointer i at the beginning of arr1 and a pointer j at the beginning of arr2. We compare the elements at these pointers and add the smaller element to our union array, making sure to skip duplicates.

Step-by-Step Evolution

At each step:

1. If arr1[i] < arr2[j]: Check if arr1[i] is already in the union array (by comparing it with the last added element). If it is not, add it. Then increment i.
2. If arr2[j] < arr1[i]: Check if arr2[j] is already in the union array. If it is not, add it. Then increment j.
3. If arr1[i] == arr2[j]: Add the element (if it is not a duplicate) and increment both pointers.
4. Once one array is fully traversed, add any remaining elements from the other array, continuing to skip duplicates.

arr1: [1, 1, 2, 3, 4, 5] | N1 = 6
arr2: [2, 3, 4, 4, 5, 6] | N2 = 6

i = 0, j = 0
- arr1[0] (1) < arr2[0] (2). Union is empty. Insert 1. i++ (i=1).
- arr1[1] (1) < arr2[0] (2). Last element in Union is 1. Duplicate! Skip insertion. i++ (i=2).
- arr1[2] (2) == arr2[0] (2). Last element is 1. Insert 2. i++ (i=3), j++ (j=1).
- arr1[3] (3) == arr2[1] (3). Last element is 2. Insert 3. i++ (i=4), j++ (j=2).
- arr1[4] (4) == arr2[2] (4). Last element is 3. Insert 4. i++ (i=5), j++ (j=3).
- arr1[5] (5) == arr2[4] (5). Last element is 4. Insert 5. i++ (i=6), j++ (j=5).
- arr1 is exhausted.
- Remaining in arr2: arr2[5] (6). Last element is 5. Insert 6. j++ (j=6).
- Both arrays exhausted.
Result Union: [1, 2, 3, 4, 5, 6]

Implementation (C++)

#include <iostream>
#include <vector>
using namespace std;

vector<int> unionOptimal(int arr1[], int n1, int arr2[], int n2) {
    int i = 0, j = 0;
    vector<int> unionArr;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            if (unionArr.size() == 0 || unionArr.back() != arr1[i]) {
                unionArr.push_back(arr1[i]);
            }
            i++;
        } else {
            if (unionArr.size() == 0 || unionArr.back() != arr2[j]) {
                unionArr.push_back(arr2[j]);
            }
            j++;
        }
    }
    
    // Copy remaining elements of arr1
    while (i < n1) {
        if (unionArr.size() == 0 || unionArr.back() != arr1[i]) {
            unionArr.push_back(arr1[i]);
        }
        i++;
    }
    
    // Copy remaining elements of arr2
    while (j < n2) {
        if (unionArr.size() == 0 || unionArr.back() != arr2[j]) {
            unionArr.push_back(arr2[j]);
        }
        j++;
    }
    
    return unionArr;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N_1 + N_2)$ because we traverse both arrays in a single pass.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space.

  Note: The space used to store and return the union array ($\mathcal{O}(N_1 + N_2)$ in the worst case) is required for the output and is not considered auxiliary space.

10. Intersection of Two Sorted Arrays: Brute Force Visited-Array Approach

The intersection of two arrays contains the elements that appear in both arrays. If an element appears multiple times in both arrays, it should appear multiple times in the intersection.

The Brute Force Algorithm

To find the intersection, we can compare each element of arr1 against the elements of arr2. To avoid matching the same element in arr2 multiple times, we maintain a visited array of size $N_2$ initialized to 0.

For each element arr1[i]:

1. Scan arr2 from the beginning.
2. If arr1[i] == arr2[j] and visited[j] == 0, add arr1[i] to the intersection, mark visited[j] = 1, and break the inner loop.
3. Since the arrays are sorted, if we encounter an element arr2[j] > arr1[i], we can break the inner loop early because no matching element can appear further down the sorted array.

Implementation (C++)

#include <iostream>
#include <vector>
using namespace std;

vector<int> intersectionBrute(int arr1[], int n1, int arr2[], int n2) {
    vector<int> intersection;
    vector<int> visited(n2, 0); // Track matched elements in arr2
    
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            if (arr1[i] == arr2[j] && visited[j] == 0) {
                intersection.push_back(arr1[i]);
                visited[j] = 1;
                break;
            }
            // Early stop optimization for sorted arrays
            if (arr2[j] > arr1[i]) {
                break;
            }
        }
    }
    return intersection;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N_1 \times N_2)$ in the worst case when there are few matches and we frequently scan the arrays.
• Space Complexity: $\mathcal{O}(N_2)$ auxiliary space to maintain the visited array.

11. Intersection of Two Sorted Arrays: Optimal Two-Pointer Approach

We can optimize the intersection of two sorted arrays to run in linear time and $\mathcal{O}(1)$ auxiliary space by using a two-pointer approach.

The Two-Pointer Mental Model

We place pointer i at the beginning of arr1 and pointer j at the beginning of arr2. Since the arrays are sorted, we can easily find matches by advancing the pointer that points to the smaller element.

Step-by-Step Evolution

At each step:

1. If arr1[i] < arr2[j]: The element arr1[i] is too small to have a match in arr2 at or after j. Increment i.
2. If arr2[j] < arr1[i]: The element arr2[j] is too small to have a match in arr1 at or after i. Increment j.
3. If arr1[i] == arr2[j]: We found a match! Add the element to the intersection array, and increment both i and j.

Implementation (C++)

#include <iostream>
#include <vector>
using namespace std;

vector<int> intersectionOptimal(int arr1[], int n1, int arr2[], int n2) {
    int i = 0, j = 0;
    vector<int> intersection;
    
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else if (arr2[j] < arr1[i]) {
            j++;
        } else {
            // Elements are equal, found a match
            intersection.push_back(arr1[i]);
            i++;
            j++;
        }
    }
    return intersection;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N_1 + N_2)$ because we traverse both arrays in a single pass.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space (excluding the space used to return the intersection array).

12. Algorithmic Complexity Synthesis

The following table summarizes the time and space complexities of the brute-force and optimal approaches for each problem discussed in this chapter.

Summary and Key Takeaways

• Modulo Arithmetic for Rotations: When rotating an array of size $N$ by $D$ places, always simplify $D$ using $D = d \pmod N$. This handles cases where $D \ge N$ and avoids unnecessary full-cycle rotations.
• The Reversal Trick: Rotating an array by $D$ places can be done in-place with $\mathcal{O}(1)$ auxiliary space by reversing the two sub-segments of the array individually, and then reversing the entire array.
• Two-Pointer Partitioning: To rearrange elements in-place (such as moving zeros to the end), use a two-pointer approach. One pointer (j) tracks the target position (e.g., the first zero), while the other pointer (i) scans the array for elements that need to be swapped.
• Leveraging Sorted Properties: When operating on sorted arrays (such as finding unions or intersections), avoid nested loops or heavy data structures like sets. Instead, use two pointers to traverse the arrays in a single pass, which reduces the time complexity to $\mathcal{O}(N_1 + N_2)$.
• Duplicate Prevention in Unions: When merging sorted arrays using two pointers, you can prevent duplicates in the output by comparing the current element with the last element added to the result array (unionArr.back()).
• Auxiliary vs. Total Space: Always distinguish between auxiliary space (extra memory used by the algorithm) and output space (memory used to store the results). For example, the optimal union algorithm uses $\mathcal{O}(1)$ auxiliary space, even though the returned result array takes $\mathcal{O}(N_1 + N_2)$ space.