Swapping Values

Overview

When solving problems, you'll often need to move items around in a data structure in order to meet some ordering criteria (e.g. sorting in ascending order). Swapping is useful because it allows you to reduce the additional space required to achieve the new ordering.

Extra Space

Let's say we want to reverse an array nums. We could do this by iterating over nums while adding each value from the opposite end of nums to a new array, reversed.

function reverseArray(nums) {
  const reversed = new Array(nums.length);
 
  for (let i = 0; i < nums.length; i++) {
    const lastIndex = nums.length - 1
    reversed[i] = nums[lastIndex - i]; // lastIndex - i corresponds to the position opposite of i
  }
 
  return reversed;
}
 
const nums = [1,2,3,4,5]
 
reverseArray(nums) // returns [5,4,3,2,1]

This works but the extra space required is directly dependent on the size of the original nums array. As the length of nums increases, so does the length of reversed, which is an inefficient use of space. We can be smarter about how much extra space we use by instead swapping values to reverse the array.

How to Swap Values

Swapping values requires overwriting them. For this reason, we need a temporary variable to store a value before we overwrite it. Given two values, A and B respectively, that need to be swapped, here's the approach:

Here's how to swap the position of the first and last value of the nums array:

const nums = [1,2,3,4,5] 
 
// 1. Assign value A to a temporary variable
let temp = nums[0] 
 
// 2. Overwrite value A with value B
nums[0] = nums[nums.length - 1]
 
// 3. Overwrite value B with temp
nums[nums.length - 1] = temp // nums is now `[5,2,3,4,1]

The use of the temp variable still requires extra space, however temp uses the same amount of space no matter how large the size of nums grows.

The above code only swaps the first and last values; if we want to reverse the entire array we need to look at the Two Pointers technique.