In-Place Element Removal

When tasked with filtering out specific values from an array in-place, allocating additional memory is often restricted. The two-pointer method provides an elegant solution by separating the reading and writing processes.

Strategy: Read and Write Pointers

We initialize two distinct indices: a write_idx to track the position where valid elements should be placed, and a read_idx to scan through the array. As we iterate, if the element at read_idx matches the target value to remove, we simply advance the reader. If it does not match, we copy the value to the write_idx position and increment both pointers. Upon completion, write_idx will represent the count of remaining elements.

int eliminateValue(int* arr, int len, int target_val) {
    int write_idx = 0;
    for (int read_idx = 0; read_idx < len; read_idx++) {
        if (arr[read_idx] != target_val) {
            arr[write_idx] = arr[read_idx];
            write_idx++;
        }
    }
    return write_idx;
}

Deduplicating a Sorted Array

To eliminate duplicate entries from a non-decreasing array without extra space, we can employ a variation of the two-pointer strategy. One pointer defines the boundary of unique elements, while the other explores the remainder of the array.

Strategy: Boundary and Scanner Pointers

Set a unique_end pointer at index 0, representing the last confirmed unique element. A scanner pointer starts at index 1 to traverse the array. Whenever arr[scanner] differs from arr[unique_end], a new unique element is found. We then advance unique_end by one and copy the value from scanner to this new position. If they are identical, the scanner just moves forward. The final count of unique items is unique_end + 1.

int filterDuplicates(int* arr, int len) {
    if (len == 0) return 0;
    
    int unique_end = 0;
    for (int scanner = 1; scanner < len; scanner++) {
        if (arr[scanner] != arr[unique_end]) {
            unique_end++;
            arr[unique_end] = arr[scanner];
        }
    }
    return unique_end + 1;
}

Merging Two Sorted Arrays

Merging two sorted arrays into the buffer of the first array can be tricky if done from the beginning, as overlapping writes could overwrite unprocessed data. Instead, populating the destination from back to front ensures data integrity.

Strategy: Reverse Three-Pointer Traversal

We utilize three indices: idx_a pointing to the last valid element in the first array, idx_b pointing to the last element of the second array, and fill_pos pointing to the very end of the first array's total capacity. During each iteration, we compare the elements at idx_a and idx_b. The larger value is placed at fill_pos, and the respective pointers are decremented. If the second array still has elements remaining after the loop, they are copied over directly.

void combineSortedArrays(int* arr_a, int capacity_a, int size_a, int* arr_b, int capacity_b, int size_b) {
    int idx_a = size_a - 1;
    int idx_b = size_b - 1;
    int fill_pos = size_a + size_b - 1;

    while (idx_a >= 0 && idx_b >= 0) {
        if (arr_a[idx_a] > arr_b[idx_b]) {
            arr_a[fill_pos--] = arr_a[idx_a--];
        } else {
            arr_a[fill_pos--] = arr_b[idx_b--];
        }
    }

    while (idx_b >= 0) {
        arr_a[fill_pos--] = arr_b[idx_b--];
    }
}