Interview Cake

In-Place Algorithm

An in-place method modifies data structures or objects outside of its own stack frame (i.e.: stored on the process heap or in the stack frame of a calling function). Because of this, the changes made by the method remain after the call completes.

In-place algorithms are sometimes called destructive, since the original input is "destroyed" (or modified) during the method call.

Careful: "In-place" does not mean "without creating any additional variables!" Rather, it means "without creating a new copy of the input." In general, an in-place method will only create additional variables that are space.

An out-of-place method doesn't make any changes that are visible to other methods. Usually, those methods copy any data structures or objects before manipulating and changing them.

In many languages, primitive values (integers, floating point numbers, or characters) are copied when passed as arguments, and more complex data structures (arrays, heaps, or hash tables) are passed by reference. In Java, arguments that are pointers can be modified in place.

Here are two methods that do the same operation on an array, except one is in-place and the other is out-of-place:

public static void squareArrayInPlace(int[] intArray) { for (int i = 0; i < intArray.length; i++) { intArray[i] *= intArray[i]; } // NOTE: no need to return anything - we modified // intArray in place } public static int[] squareArrayOutOfPlace(int[] intArray) { // we allocate a new array with the length of the input array int[] squaredArray = new int[intArray.length]; for (int i = 0; i < intArray.length; i++) { squaredArray[i] = (int) Math.pow(intArray[i], 2); } return squaredArray; }

Working in-place is a good way to save time and space. An in-place algorithm avoids the cost of initializing or copying data structures, and it usually has an space cost.

But be careful: an in-place algorithm can cause side effects. Your input is "destroyed" or "altered," which can affect code outside of your method. For example:

int[] originalArray = new int[]{2, 3, 4, 5}; squareArrayInPlace(originalArray); System.out.println("original array: " + Arrays.toString(originalArray)); // prints: original array: [4, 9, 16, 25], confusingly!

Generally, out-of-place algorithms are considered safer because they avoid side effects. You should only use an in-place algorithm if you're space constrained or you're positive you don't need the original input anymore, even for debugging.

. . .