In-place modification refers to operations pefrormed directly on the original data structure without allocating new storage. For duplicate removal, a naive approach would involve creating a new array to store unique elements, but in-place constraints require modifying the existing array and returning its new effective length.

When dealing with a sorted array, duplicate elements are contiguous. A straightforward deletion of each duplicate would lead to repeated data shifts, resulting in O(N²) time complexity. The two-pointer technique offers an efficient solution.

A slow pointer (slow) tracks the position for the next unique element, while a fast pointer (fast) scans ahead. When fast encounters a value different from nums[slow], the value is copied to nums[++slow]. After fast traverses the array, elements from nums[0] to nums[slow] are unique.

#include <stdio.h>

int deduplicateSortedArray(int* arr, int len) {
    if (len == 0) return 0;
    int tracker = 0, scanner = 0;
    while (scanner < len) {
        if (arr[scanner] != arr[tracker]) {
            tracker++;
            arr[tracker] = arr[scanner];
        }
        scanner++;
    }
    return tracker + 1;
}

int main() {
    int data[] = {0, 0, 1, 1, 2, 3, 3, 4};
    int size = sizeof(data) / sizeof(data[0]);

    int newLength = deduplicateSortedArray(data, size);

    printf("New length: %d\n", newLength);
    printf("Processed array: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

The same logic applies to sorted linked lists, replacing array assignments with pointer mainpulations.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node* next;
} ListNode;

ListNode* deduplicateSortedList(ListNode* head) {
    if (head == NULL) return NULL;
    ListNode* current = head;
    ListNode* explorer = head->next;
    while (explorer != NULL) {
        if (explorer->value != current->value) {
            current->next = explorer;
            current = current->next;
        }
        explorer = explorer->next;
    }
    current->next = NULL;
    return head;
}

ListNode* createListNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->value = val;
    node->next = NULL;
    return node;
}

void printList(ListNode* head) {
    ListNode* cursor = head;
    while (cursor != NULL) {
        printf("%d ", cursor->value);
        cursor = cursor->next;
    }
    printf("\n");
}

int main() {
    ListNode* head = createListNode(1);
    head->next = createListNode(1);
    head->next->next = createListNode(2);
    head->next->next->next = createListNode(2);
    head->next->next->next->next = createListNode(3);

    printf("Initial list: ");
    printList(head);

    ListNode* result = deduplicateSortedList(head);
    printf("Deduplicated list: ");
    printList(result);

    return 0;
}

Removing Specific Elements In-Place

For removing all instances of a given value from an array, the two-pointer method is again applicable. The fast pointer scans elements; when it finds a value not equal to the target, it copies it to the slow pointer's position, advancing the slow pointer.

#include <stdio.h>

int filterOutValue(int* arr, int len, int target) {
    int writer = 0, reader = 0;
    while (reader < len) {
        if (arr[reader] != target) {
            arr[writer] = arr[reader];
            writer++;
        }
        reader++;
    }
    return writer;
}

int main() {
    int data[] = {1, 2, 3, 2, 4, 2, 5};
    int targetVal = 2;
    int size = sizeof(data) / sizeof(data[0]);

    printf("Original: ");
    for (int i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");

    int newLen = filterOutValue(data, size, targetVal);

    printf("After removing %d: ", targetVal);
    for (int i = 0; i < newLen; i++) printf("%d ", data[i]);
    printf("\n");
    return 0;
}

Moving Zeroes to the End

This problem can be solved by first removing all zeroes using the filterOutValue function, then filling the remaining positions at the end of the array with zeroes.

#include <stdio.h>

int filterOutValue(int* arr, int len, int target) {
    int writer = 0, reader = 0;
    while (reader < len) {
        if (arr[reader] != target) {
            arr[writer] = arr[reader];
            writer++;
        }
        reader++;
    }
    return writer;
}

void relocateZeroes(int* arr, int len) {
    int nonZeroCount = filterOutValue(arr, len, 0);
    for (int i = nonZeroCount; i < len; i++) {
        arr[i] = 0;
    }
}

int main() {
    int data[] = {0, 5, 0, 7, 9, 0, 1};
    int size = sizeof(data) / sizeof(data[0]);

    printf("Before: ");
    for (int i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");

    relocateZeroes(data, size);

    printf("After: ");
    for (int i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");
    return 0;
}

Common Left-Right Pointer Patterns

1. Binary Search

int findIndex(int* sortedArr, int len, int key) {
    int start = 0, end = len - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (sortedArr[mid] == key) return mid;
        else if (sortedArr[mid] < key) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
}

2. Two-Sum on Sorted Array Given a sorted array, find two numbers that add up to a specific target.

#include <stdio.h>

typedef struct {
    int pos1;
    int pos2;
} IndexPair;

IndexPair findPairWithSum(int* sortedArr, int len, int targetSum) {
    int left = 0, right = len - 1;
    while (left < right) {
        int currentSum = sortedArr[left] + sortedArr[right];
        if (currentSum == targetSum) {
            IndexPair pair = {left + 1, right + 1};
            return pair;
        } else if (currentSum < targetSum) {
            left++;
        } else {
            right--;
        }
    }
    IndexPair pair = {-1, -1};
    return pair;
}

int main() {
    int data[] = {1, 3, 5, 8, 11};
    int target = 9;
    int size = sizeof(data) / sizeof(data[0]);

    IndexPair result = findPairWithSum(data, size, target);
    if (result.pos1 != -1) {
        printf("Elements at indices %d and %d sum to %d.\n", result.pos1, result.pos2, target);
    } else {
        printf("No valid pair found.\n");
    }
    return 0;
}

3. Array Reversal

#include <stdio.h>
#include <string.h>

void invertArray(char* str) {
    int low = 0, high = strlen(str) - 1;
    while (low < high) {
        char swapTemp = str[low];
        str[low] = str[high];
        str[high] = swapTemp;
        low++;
        high--;
    }
}

int main() {
    char message[] = "algorithm";
    printf("Original: %s\n", message);
    invertArray(message);
    printf("Reversed: %s\n", message);
    return 0;
}

4. Palindrome Verification A palindrome reads the same forwards and backwards.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool checkPalindrome(char* str) {
    int start = 0, end = strlen(str) - 1;
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

int main() {
    char test1[] = "racecar";
    char test2[] = "hello";
    printf("\"%s\" is a palindrome? %s\n", test1, checkPalindrome(test1) ? "Yes" : "No");
    printf("\"%s\" is a palindrome? %s\n", test2, checkPalindrome(test2) ? "Yes" : "No");
    return 0;
}