Two Pointers | Problems in Arrays - 2 | Lecture 15 | C++ and DSA Foundation Course

Key Concepts

• Arrays: Data structures that store a collection of elements of the same type in contiguous memory locations.
• Two Pointers Pattern: An algorithmic technique that uses two pointers to traverse a data structure (like an array) simultaneously, often from opposite ends, to solve problems efficiently.
• In-place Sorting: Sorting an array without using extra space, modifying the original array directly.
• Pass by Reference: Passing a variable to a function in such a way that the function can modify the original variable.
• For-each Loop: A loop that iterates over each element in a collection (like an array or vector).
• Parity: Whether an integer is even or odd.
• Non-decreasing Order: A sequence where each element is greater than or equal to the previous element.
• Absolute Value: The non-negative value of a number, regardless of its sign.
• Prefix Sum: (Mentioned for the next lecture) A technique where a new array is created, storing the cumulative sum of elements up to each index in the original array.

Sorting an Array Consisting of Only Zeros and Ones

Problem Statement

Given an array containing only zeros and ones, sort the array such that all zeros are placed at the beginning (left side) and all ones are placed at the end (right side).

Basic Approach (Counting Zeros)

1. Count Zeros: Traverse the array once to count the number of zeros.
2. Populate Array: Traverse the array again. Fill the first count positions with zeros and the remaining positions with ones.

Code Implementation (Counting Zeros)

#include <iostream>
#include <vector>

using namespace std;

void sortZeroOne(vector<int>& arr) {
    int zerosCount = 0;
    for (int element : arr) {
        if (element == 0) {
            zerosCount++;
        }
    }

    for (int i = 0; i < arr.size(); i++) {
        if (i < zerosCount) {
            arr[i] = 0;
        } else {
            arr[i] = 1;
        }
    }
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;

    vector<int> arr(n);
    cout << "Enter the elements (0 or 1): ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sortZeroOne(arr);

    cout << "Sorted array: ";
    for (int element : arr) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

Two Pointers Approach

1. Initialize Pointers: Set a left pointer to the beginning of the array (index 0) and a right pointer to the end of the array (index n-1).
2. Traverse and Swap:
   • While left < right:
     • If arr[left] == 1 and arr[right] == 0, swap arr[left] and arr[right], increment left, and decrement right.
     • If arr[left] == 0, increment left.
     • If arr[right] == 1, decrement right.

Code Implementation (Two Pointers)

#include <iostream>
#include <vector>

using namespace std;

void sortZeroOneTwoPointers(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        if (arr[left] == 1 && arr[right] == 0) {
            swap(arr[left], arr[right]);
            left++;
            right--;
        } else {
            if (arr[left] == 0) {
                left++;
            }
            if (arr[right] == 1) {
                right--;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;

    vector<int> arr(n);
    cout << "Enter the elements (0 or 1): ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sortZeroOneTwoPointers(arr);

    cout << "Sorted array: ";
    for (int element : arr) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

Analysis

• The two-pointer approach is more efficient as it traverses the array only once, resulting in a time complexity of O(n).
• The counting approach requires two traversals, also resulting in O(n) time complexity, but with a higher constant factor.

Sorting an Array by Parity

Problem Statement

Given an array of integers, sort the array such that all even integers are placed at the beginning (left side) and all odd integers are placed at the end (right side). The relative order of even and odd integers does not matter.

Two Pointers Approach

1. Initialize Pointers: Set a left pointer to the beginning of the array (index 0) and a right pointer to the end of the array (index n-1).
2. Traverse and Swap:
   • While left < right:
     • If arr[left] is odd and arr[right] is even, swap arr[left] and arr[right], increment left, and decrement right.
     • If arr[left] is even, increment left.
     • If arr[right] is odd, decrement right.

Code Implementation

#include <iostream>
#include <vector>

using namespace std;

void sortByParity(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        if (arr[left] % 2 != 0 && arr[right] % 2 == 0) {
            swap(arr[left], arr[right]);
            left++;
            right--;
        } else {
            if (arr[left] % 2 == 0) {
                left++;
            }
            if (arr[right] % 2 != 0) {
                right--;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;

    vector<int> arr(n);
    cout << "Enter the elements: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sortByParity(arr);

    cout << "Sorted array: ";
    for (int element : arr) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

Sorted Squares

Problem Statement

Given a sorted array of integers in non-decreasing order, return an array of the squares of each number, also in non-decreasing order.

Key Insight

The square of a negative number is positive. Therefore, the largest square can be either the square of the smallest (most negative) number or the square of the largest (most positive) number.

Two Pointers Approach

1. Initialize Pointers: Set a left pointer to the beginning of the array (index 0) and a right pointer to the end of the array (index n-1).
2. Create Result Array: Create a new array result of the same size as the input array.
3. Traverse and Populate:
   • While left <= right:
     • Compare the absolute values of arr[left] and arr[right].
     • If abs(arr[left]) > abs(arr[right]), the square of arr[left] is the next largest square. Add arr[left] * arr[left] to the result array and increment left.
     • Otherwise, the square of arr[right] is the next largest square. Add arr[right] * arr[right] to the result array and decrement right.
4. Reverse Result: Reverse the result array to obtain the squares in non-decreasing order.

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> sortedSquares(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n);
    int left = 0;
    int right = n - 1;
    int k = 0;

    while (left <= right) {
        if (abs(arr[left]) > abs(arr[right])) {
            result[k++] = arr[left] * arr[left];
            left++;
        } else {
            result[k++] = arr[right] * arr[right];
            right--;
        }
    }

    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;

    vector<int> arr(n);
    cout << "Enter the elements (sorted in non-decreasing order): ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<int> squaredArr = sortedSquares(arr);

    cout << "Sorted squares: ";
    for (int element : squaredArr) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

Analysis

• The two-pointer approach efficiently finds the largest squares in each iteration, resulting in a time complexity of O(n).
• Reversing the array takes O(n) time, but it's still linear.

Conclusion

The lecture focused on applying the two-pointer pattern to solve array-related problems. The examples demonstrated how to use two pointers to efficiently sort arrays based on specific criteria (zeros and ones, parity) and to generate sorted arrays of squares. The key takeaway is that the two-pointer approach can significantly improve the efficiency of array manipulation algorithms by reducing the number of traversals required. The lecture also emphasized the importance of dry-running code to identify potential issues and ensure correctness.