Inplace Modification

In-place modification refers to algorithms that modify or transform input data structures without creating copies or new structures. This saves additional memory allocation.

Java example - Rotate array in-place:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void rotate(int[] arr, int k) {
  k %= arr.length; 
  reverse(arr, 0, arr.length - 1);
  reverse(arr, 0, k - 1);
  reverse(arr, k, arr.length - 1);
}

void reverse(int[] arr, int i, int j) {
  while (i < j) {
    int temp = arr[i];
    arr[i++] = arr[j];
    arr[j--] = temp;
  }
}

C++ example - Sort linked list in-place:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

ListNode* sortList(ListNode* head) {
  if (!head || !head->next) return head;

  // Split into halves 
  ListNode* mid = getMid(head);
  ListNode* left = sortList(head); 
  ListNode* right = sortList(mid);

  // Merge halves 
  return merge(left, right);
}

ListNode* merge(ListNode* l1, ListNode* l2) {
  ListNode dummy;
  ListNode* tail = &dummy;
  
  // in-place merging logic
  return dummy.next;
}

Python example - Reverse string in-place:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def reverse(s):
  left = 0
  right = len(s) - 1
  
  while left < right:
    s[left], s[right] = s[right], s[left]
    left += 1
    right -= 1
  
  return s

In-place modification saves memory by mutating existing structures. Useful when extra space is constrained.

Inplace modification refers to the practice of modifying the data structure directly, without using extra space for a copy or auxiliary data structure. The main advantage of inplace modification is that it’s space-efficient, but it requires careful handling since changes to the data are often irreversible. Common examples include reversing an array, sorting an array, or modifying elements based on certain conditions, all without using additional memory.

Solution

Below are examples of reversing an array using inplace modification in Java, C++, and Python.

Java

1
2
3
4
5
6
7
8

public static void reverseArray(int[] array) {
  int n = array.length;
  for(int i = 0; i < n / 2; i++) {
    int temp = array[i];
    array[i] = array[n - i - 1];
    array[n - i - 1] = temp;
  }
}

This Java code snippet reverses an array of integers by swapping the first and last elements, then the second and second-to-last elements, and so on. It does this without needing any extra space beyond a temporary variable for swapping.

C++

1
2
3
4
5
6
7

#include <algorithm>

void reverseArray(int arr[], int n) {
  for(int i = 0; i < n / 2; i++) {
    std::swap(arr[i], arr[n - i - 1]);
  }
}

Similar to the Java code, the C++ version uses the standard library function std::swap to reverse the array in place.

Python

1
2
3
4

def reverseArray(arr):
  n = len(arr)
  for i in range(n // 2):
    arr[i], arr[n - i - 1] = arr[n - i - 1], arr[i]

In Python, tuple unpacking is used to perform the swaps in place, reversing the array.

Key Takeaways

Inplace modification allows operations to be performed directly on a data structure without additional memory allocation. It’s efficient but can be tricky, as mistakes may lead to irreversible changes. The example above of reversing an array showcases the typical structure of an inplace modification, where elements are swapped or modified directly within the original data structure.