[AlgoMastery]
Topics›Array›In-Place Operations
📖

In-Place Operations

Array
~20 min read
5 practice problems

Overview

In-Place Operations modify arrays without using extra space proportional to input size. Instead of creating new arrays, elements are rearranged, swapped, or overwritten within the existing array structure. This achieves O(1) space complexity, crucial for memory-constrained environments.

The key principle: use the array itself as both input and output, leveraging indices and swaps to reorganize elements efficiently.

In-place operations are particularly useful for:

  • Removing duplicates
  • Moving zeros/elements
  • Partitioning arrays
  • Reversing arrays
  • Sorting algorithms
  • Space-optimized solutions

Pattern 1: Remove Duplicates from Sorted Array

Remove duplicates in-place, return new length.

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  
  let writeIndex = 1;
  
  for (let readIndex = 1; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== nums[readIndex - 1]) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }
  
  return writeIndex;
}

Time: O(n), Space: O(1)

Allow at most 2 duplicates:

function removeDuplicatesAtMostTwo(nums: number[]): number {
  if (nums.length <= 2) return nums.length;
  
  let writeIndex = 2;
  
  for (let readIndex = 2; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== nums[writeIndex - 2]) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }
  
  return writeIndex;
}

Time: O(n), Space: O(1)

Pattern 2: Remove Element

Remove all instances of value in-place.

function removeElement(nums: number[], val: number): number {
  let writeIndex = 0;
  
  for (let readIndex = 0; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== val) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }
  
  return writeIndex;
}

Time: O(n), Space: O(1)

Two-pointer approach (when val is rare):

function removeElementTwoPointers(nums: number[], val: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    if (nums[left] === val) {
      nums[left] = nums[right];
      right--;
    } else {
      left++;
    }
  }
  
  return left;
}

Time: O(n), Space: O(1)

Pattern 3: Move Zeros to End

Move all zeros to end while maintaining relative order of non-zeros.

function moveZeroes(nums: number[]): void {
  let writeIndex = 0;
  
  // Move all non-zero elements forward
  for (let readIndex = 0; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== 0) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }
  
  // Fill remaining positions with zeros
  while (writeIndex < nums.length) {
    nums[writeIndex] = 0;
    writeIndex++;
  }
}

Time: O(n), Space: O(1)

Optimized (single pass):

function moveZeroesOptimized(nums: number[]): void {
  let writeIndex = 0;
  
  for (let readIndex = 0; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== 0) {
      if (readIndex !== writeIndex) {
        [nums[readIndex], nums[writeIndex]] = [nums[writeIndex], nums[readIndex]];
      }
      writeIndex++;
    }
  }
}

Time: O(n), Space: O(1)

Pattern 4: Partition Array

Partition array around a pivot value.

function partition(nums: number[], pivot: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    while (left <= right && nums[left] < pivot) left++;
    while (left <= right && nums[right] >= pivot) right--;
    
    if (left <= right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
  
  return left; // Index where partition occurs
}

Time: O(n), Space: O(1)

Partition into three regions (<, =, >):

function partitionThreeWay(nums: number[], pivot: number): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (nums[mid] < pivot) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === pivot) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time: O(n), Space: O(1)

Pattern 5: Reverse Array

Reverse array in-place.

function reverseArray(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
}

Time: O(n), Space: O(1)

Reverse array between indices:

function reverseRange(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start++;
    end--;
  }
}

Pattern 6: Sort Colors (Dutch National Flag)

Sort array of 0s, 1s, and 2s in-place.

function sortColors(nums: number[]): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time: O(n), Space: O(1)

Generalized for K colors:

function sortKColors(nums: number[], k: number): void {
  let left = 0;
  
  for (let color = 0; color < k - 1; color++) {
    let right = nums.length - 1;
    
    while (left <= right) {
      if (nums[left] === color) {
        left++;
      } else if (nums[right] === color) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
      } else {
        right--;
      }
    }
  }
}

Time: O(n * k), Space: O(1)

Pattern 7: Merge Sorted Arrays

Merge two sorted arrays in-place (first array has enough space).

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;
  
  // Merge from end
  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i];
      i--;
    } else {
      nums1[k] = nums2[j];
      j--;
    }
    k--;
  }
  
  // Copy remaining elements from nums2
  while (j >= 0) {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
}

Time: O(m + n), Space: O(1)

Pattern 8: First Missing Positive

Find smallest missing positive integer in-place.

function firstMissingPositive(nums: number[]): number {
  const n = nums.length;
  
  // Mark numbers outside range [1, n] as n+1
  for (let i = 0; i < n; i++) {
    if (nums[i] <= 0 || nums[i] > n) {
      nums[i] = n + 1;
    }
  }
  
  // Use array as hash: mark presence by making value negative
  for (let i = 0; i < n; i++) {
    const num = Math.abs(nums[i]);
    if (num <= n && nums[num - 1] > 0) {
      nums[num - 1] = -nums[num - 1];
    }
  }
  
  // Find first positive index
  for (let i = 0; i < n; i++) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  
  return n + 1;
}

Time: O(n), Space: O(1)

Explanation: Use array indices as hash keys, mark presence by negating values.

Pattern 9: Set Matrix Zeroes

Set entire row and column to zero if element is zero.

function setZeroes(matrix: number[][]): void {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRowHasZero = false;
  let firstColHasZero = false;
  
  // Check if first row/col has zero
  for (let j = 0; j < cols; j++) {
    if (matrix[0][j] === 0) firstRowHasZero = true;
  }
  for (let i = 0; i < rows; i++) {
    if (matrix[i][0] === 0) firstColHasZero = true;
  }
  
  // Use first row/col as markers
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }
  
  // Set zeros based on markers
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }
  
  // Set first row/col
  if (firstRowHasZero) {
    for (let j = 0; j < cols; j++) matrix[0][j] = 0;
  }
  if (firstColHasZero) {
    for (let i = 0; i < rows; i++) matrix[i][0] = 0;
  }
}

Time: O(rows * cols), Space: O(1)

Pattern 10: Wiggle Sort

Rearrange array so nums[0] < nums[1] > nums[2] < nums[3]...

function wiggleSort(nums: number[]): void {
  for (let i = 1; i < nums.length; i++) {
    if ((i % 2 === 1 && nums[i] < nums[i - 1]) ||
        (i % 2 === 0 && nums[i] > nums[i - 1])) {
      [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
    }
  }
}

Time: O(n), Space: O(1)

Wiggle Sort II (strict alternation):

function wiggleSortII(nums: number[]): void {
  const sorted = [...nums].sort((a, b) => a - b);
  const n = nums.length;
  const mid = Math.floor((n + 1) / 2);
  
  // Interleave smaller and larger halves
  for (let i = 0; i < n; i++) {
    if (i % 2 === 0) {
      nums[i] = sorted[mid - 1 - Math.floor(i / 2)];
    } else {
      nums[i] = sorted[n - 1 - Math.floor(i / 2)];
    }
  }
}

Time: O(n log n), Space: O(n) for sorting

Pattern 11: Move All Odd Numbers Before Even

Move all odd numbers before even numbers.

function moveOddBeforeEven(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    // Find first even from left
    while (left < right && nums[left] % 2 === 1) left++;
    // Find first odd from right
    while (left < right && nums[right] % 2 === 0) right--;
    
    if (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
}

Time: O(n), Space: O(1)

Pattern 12: Rearrange Positive and Negative

Rearrange array so negatives come before positives.

function rearrangePosNeg(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    while (left < right && nums[left] < 0) left++;
    while (left < right && nums[right] >= 0) right--;
    
    if (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
}

Time: O(n), Space: O(1)

Maintain relative order:

function rearrangePosNegStable(nums: number[]): void {
  // Use two-pointer approach
  let writeIndex = 0;
  
  // First pass: move negatives
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 0) {
      if (i !== writeIndex) {
        // Shift elements
        const temp = nums[i];
        for (let j = i; j > writeIndex; j--) {
          nums[j] = nums[j - 1];
        }
        nums[writeIndex] = temp;
      }
      writeIndex++;
    }
  }
}

Time: O(n²), Space: O(1)

When to Use In-Place Operations

Use in-place operations when:

  • Space constraint - O(1) space required
  • Memory optimization - Large arrays, limited memory
  • Modify existing array - Don't need original
  • Interview constraints - Often asked for in-place solutions
  • Performance - Avoid copying large arrays
  • Real-time systems - Memory-efficient processing

Key principle: Use read/write pointers or two pointers to reorganize elements without extra space.

Template (Read-Write Pointer)

function inPlaceTemplate(nums: number[]): number {
  let writeIndex = 0;
  
  for (let readIndex = 0; readIndex < nums.length; readIndex++) {
    if (/* condition to keep element */) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }
  
  return writeIndex; // New length
}

Template (Two Pointers)

function twoPointerTemplate(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    // Move left pointer
    while (left < right && /* condition */) left++;
    // Move right pointer
    while (left < right && /* condition */) right--;
    
    if (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
}

Time and Space Complexity Summary

  • Remove duplicates: O(n) time, O(1) space
  • Move zeros: O(n) time, O(1) space
  • Partition: O(n) time, O(1) space
  • Sort colors: O(n) time, O(1) space
  • Merge arrays: O(m + n) time, O(1) space
  • Set matrix zeros: O(rows * cols) time, O(1) space
  • First missing positive: O(n) time, O(1) space

Practice Tips

  1. Read-write pointers - For filtering/removing elements
  2. Two pointers - For partitioning/swapping
  3. Use array as hash - For marking presence
  4. Merge from end - When one array has extra space
  5. Markers in place - Use existing array for flags

Common Mistakes

  1. Index errors - Off-by-one in read/write indices
  2. Not updating pointers - Forgetting to increment/decrement
  3. Boundary conditions - Not handling empty arrays
  4. Overwriting data - Writing before reading needed data
  5. Stable vs unstable - Not maintaining relative order when needed

Related Concepts

  • Two Pointers - Core technique for in-place operations
  • Partitioning - Dividing array into regions
  • Swapping - Exchanging elements efficiently
  • Read-Write Pattern - Filtering elements in-place

In-place operations are essential for space-efficient algorithms. Master these patterns, and you'll solve many array problems with optimal space complexity in coding interviews.

← PreviousArray RotationNext →Merge Intervals