Working with arrays is a cornerstone of algorithm development. This article delves into several effective strategies for managing and manipulating array data, including binary search for rapid element lookup and various two-pointer methodologies for in-place modifications and optimized transformations.

704. Binary Search

Binary search is an essential algorithm for finding an element's index within a sorted array. Its efficiency, with a time complexity of O(log N), makes it a preferred choice over linear scans for large datasets. The core idea is to repeatedly divide the search interval in half.

When implementing binary search, correctly managing the search interval boundaries is critical to avoid off-by-one errors or infinite loops. A common and robust approach is the "left-closed, right-closed" interval [start, end].

• Initialize start to 0 and end to nums.size() - 1.
• The loop condition is while (start <= end), indicating that the search space still includes at least one element.
• Calculate the middle index: mid = start + (end - start) / 2. This calculation prevents potential integer overflow that could occur with (start + end) / 2 if start and end are very large.
• If target is found at nums[mid], return mid.
• If target > nums[mid], the target must be in the right half, so update start = mid + 1.
• If target < nums[mid], the target must be in the left half, so update end = mid - 1.
• If the loop finishes without finding the target, return -1.

Example: Binary Search Implementation

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int leftBoundary = 0;
        int rightBoundary = nums.size() - 1;

        while (leftBoundary <= rightBoundary) { // Search space is [leftBoundary, rightBoundary]
            int midIndex = leftBoundary + (rightBoundary - leftBoundary) / 2; // Prevent overflow

            if (nums[midIndex] == target) {
                return midIndex; // Target found
            } else if (nums[midIndex] < target) {
                leftBoundary = midIndex + 1; // Target is in the right half
            } else { // nums[midIndex] > target
                rightBoundary = midIndex - 1; // Target is in the left half
            }
        }
        return -1; // Target not found
    }
};

27. Remove Element

This problem challenges us to remove all occurrences of a specific value from an array in-place, meaning without allocating extra space for a new array. The relative order of the remaining elements can be changed, and we only need to return the count of elements that are not equal to the specified value.

A highly efficient approach uses two pointers, one from each end of the array. This method minimizes element moves:

• Initialize leftPtr to 0 and rightPtr to nums.size() (note: nums.size() is exclusive, pointing one past the last element).
• Iterate while leftPtr < rightPtr.
• If nums[leftPtr] is equal to the value to be removed:
  • Replace nums[leftPtr] with the element at nums[rightPtr - 1].
  • Decrement rightPtr, effective shrinking the array from the right. We do not increment leftPtr yet because the new element at nums[leftPtr] might also be the value to be removed, and needs to be checked.
• If nums[leftPtr] is not equal to the value to be removed, simply increment leftPtr, as this element can stay.
• The final value of leftPtr (or rightPtr) will represent the number of elements not equal to the specified value.

Example: In-place Element Removal

class Solution {
public:
    int removeElement(std::vector<int>& nums, int val) {
        int currentWriteIndex = 0;
        int effectiveEnd = nums.size(); // Represents the "logical" end of the array, elements at or beyond this index are considered removed

        while (currentWriteIndex < effectiveEnd) {
            if (nums[currentWriteIndex] == val) {
                // If the element at currentWriteIndex is the value to remove,
                // replace it with the last effective element and shrink the effective end.
                nums[currentWriteIndex] = nums[effectiveEnd - 1];
                effectiveEnd--; // Shrink the array from the right
            } else {
                // If the element is not the value to remove, keep it and move to the next.
                currentWriteIndex++;
            }
        }
        return currentWriteIndex; // currentWriteIndex will be the count of elements not equal to val
    }
};

977. Squares of a Sorted Array

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

A straightforward approach would be to square each number and then sort the resulting array. While correct, this method has a time complexity of O(N log N) due to the sorting step, which can be inefficient for large arrays.

A more optimal solution leverages the fact that the original array is sorted. When squaring the numbers, the largest squared values will always originate from the elements at the extreme ends (either the leftmost or the rightmost) of the original array, due to the nature of squaring negative and positive numbers. This observation alows for a two-pointer approach that populates the result array from its end, ensuring it's sorted without a separate sort operation.

• Initialize leftPointer to 0 and rightPointer to nums.size() - 1.
• Create a new result array squaredNums of the same size.
• Initialize resultIndex to nums.size() - 1, as we will fill the squaredNums array from the end.
• While leftPointer <= rightPointer:
  • Calculate the square of the element at leftPointer (leftSquare = nums[leftPointer] * nums[leftPointer]).
  • Calculate the square of the element at rightPointer (rightSquare = nums[rightPointer] * nums[rightPointer]).
  • Compare leftSquare and rightSquare. The larger of the two is the largest squared value not yet placed in squaredNums.
  • Place the larger square into squaredNums[resultIndex].
  • If leftSquare was larger, increment leftPointer. Otherwise, decrement rightPointer.
  • Decrement resultIndex to move to the next position in the result array.
• Return the squaredNums array. This approach has a time complexity of O(N) because each element is processed once.

Example: Sorted Squares with Two Pointers

class Solution {
public:
    std::vector<int> sortedSquares(std::vector<int>& nums) {
        int arrayLength = nums.size();
        std::vector<int> squaredResults(arrayLength); // Result array of the same size

        int leftEnd = 0;
        int rightEnd = arrayLength - 1;
        int currentWritePosition = arrayLength - 1; // Fill from the end of the result array

        while (leftEnd <= rightEnd) {
            int squareOfLeft = nums[leftEnd] * nums[leftEnd];
            int squareOfRight = nums[rightEnd] * nums[rightEnd];

            if (squareOfLeft > squareOfRight) {
                squaredResults[currentWritePosition] = squareOfLeft;
                leftEnd++; // Move left pointer inward
            } else {
                squaredResults[currentWritePosition] = squareOfRight;
                rightEnd--; // Move right pointer inward
            }
            currentWritePosition--; // Move to the next position in the result array
        }
        return squaredResults;
    }
};