Rearranging data without asking for more memory.
An array is just a contiguous block of memory. We can access any element instantly by its index, but inserting or deleting takes time because we have to shift everything over. To avoid allocating extra memory (O(1) extra space), we can rearrange elements in-place by carefully swapping values between two or three pointers.
A classic example is the Dutch National Flag problem: partitioning an array into three regions (e.g., less than, equal to, and greater than a pivot).
We maintain three pointers: low (boundary of 0s), mid (current element), and high (boundary of 2s). We examine arr[mid] and swap it to its correct region, expanding that region.
def sortColors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return numsWe only pass through the array once. The swaps happen in place, so we don't need to allocate a new array of size N.
high, we decrement high but we do not increment mid. The element swapped in from the right hasn't been examined yet!mid <= high (inclusive). If we stop at mid < high, we leave the last element unexamined.0 to len - 1.