Arrays

An array is a sequence of variables of the same type arranged contiguously in a block of memory. They provide random access fixed storage. This means that if you know the index of the element you want, retrieving it requires only O(1). However, if you don't know the index, searching for the element still requires O(n) time.

Also, it is costly to insert or delete data in the middle of an array. Because an array is a block of contiguous memory, it’s not possible to create or eliminate storage between any two elements like a linked list. Instead, you must physically move data within the array to make room for an insertion or to close the gap left by a deletion.

The length of the array is fixed; in order to store more elements than the size of the array, you must copy the contents of the current array over to a larger array, which is an expensive operation. But you also can't just declare a huge array because memory is allocated for each element even if nothing is contained in that element. As a result, use arrays when you have a good idea of how many elements need to be stored.

Keep in mind that arrays are of fixed length. As a result, some problems are more efficiently solved when working from right to left instead of left to right.

Practice: Given an unsorted array of size n containing the integers 1 through n in random order with one element randomly replaced by 0, determine the missing element most efficiently.

One solution involves sorting the array in order, but when done naively it takes O(n log n) via quicksort or mergesort. There are faster sorting methods for special cases which reduces the sorting time to linear complexity; there is an example later on in this section. However, it's not the fastest solution.

The fastest solution involves mathematical manipulations. Sum the integers from 1 through n, which will yield n(n+1)/2. Then subtract each integer that is in the array from the result. The number that remains is the integer that is missing from the array. This algorithm only requires linear time to look through the array and is optimal because each value in the array must be examined to determine the missing number.

For example: {2, 8, 0, 7, 3, 4, 6, 1}
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = n(n+1)/2 = (8*9)/2 = 36
36 - 2 - 8 - 7 - 3 - 4 - 6 - 1 = 5
5 must be the missing int.

Practice: Given an unsorted array of size n containing objects with ids of 0 … n-1, sort the array in place and in linear time. Assume that the objects contain large members such as binary data, so instantiating new copies of the objects is prohibitively expensive.

Well, a traditional comparison sort like quicksort is too slow since it requires O(n log n). However, there’s probably a way to take advantage of the limits imposed by the problem.

We’re supposed to do this in place, so the trivial solution of making another empty array of the same length (a2) and copying each value in the original array (a1) into the corresponding index doesn't work. This requirement has a real world application if you were sorting objects by field instead of just integers, but to keep the problem simple we'll just work on integers.

After some consideration, it looks like performing the sort in place is definitely possible, by continually swapping elements at each index until the correct element is in its rightful position. A coded solution in C looks like the following:

void linearSort(int* input, const int n) {
    for (int i = 0; i < n; i++) {
        while (input[i] != i) {
            // swap
            int swapPoint = input[i];
            input[i] = input[swapPoint];
            input[swapPoint] = swapPoint;
        }
    }
}

Practice Question: Write an iterative binary search for integers.

Binary search is O(log n) on sorted arrays but not on sorted linked lists because of the ability to randomly access memory in arrays. The concept is simple: divide and conquer by splitting the search space in half and eliminating the half each time that doesn’t contain the target.

Start by defining the search space as two array indexes: left and right. Initialize them to the first and last array index, and then find the middle index that divides the array approximately in half. If the array is of even length, integer division will help to truncate the middle index value. Determine whether the target is between the values at first and middle or middle and last. If the target is between first and middle, set last to middle and repeat the process. Likewise, if the target is between middle and last, set first to middle and repeat. Stop when the target is found at the middle index, or when either the left or right index has crossed with the middle index, which means that the target isn’t in the array.

public static int iterativeBinarySearch(int[] search, int target) {
    int left = 0;
    int right = search.length;
    int middle = (left + right) / 2;
 
    while (true) {
        if (search[middle] == target)
            return middle;
 
        if (left == middle || right == middle) {
            return -1;
        }
 
        if (search[middle] < target) {
            left = middle;
            middle = (left + right) / 2;
        }
 
        if (search[middle] > target) {
            right = middle;
            middle = (left + right) / 2;
        }
    }
}

Sample Question: Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. Do this in linear time and in-place.

Example:
array1 = {1, 3, 6}
array2 = {2, 4, 5, _, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

This seems like a sub-problem in mergesort, and it is, but with a twist. The first reaction is to go from left to right and swap so that the smallest elements are at the beginning of array2 and the bigger elements are in array1, then combining array1 into the end of array2.

However, there’s an easier way if you go from right to left. Since you know that the two arrays are already sorted, start at index n-1 for both arrays and compare from there, placing the larger of the two at the end of array2 and moving left as you progress.

The hardest part is figuring out when and how to stop the loop. Once you work backwards and reach the first element of one of the arrays, then just copy the elements from the other array in reverse order to finish.

public static int[] mergeArrays(int[] a, int[] b) {
    int aIndex = a.length - 1;
    int bIndex = a.length - 1;
    int cIndex = b.length - 1;
 
    while (aIndex >= 0 && bIndex >= 0) {
        if (a[aIndex] > b[bIndex]) 
            b[cIndex--] = a[aIndex--];
        else
            b[cIndex--] = b[bIndex--];
    }
 
    while (aIndex >= 0) {
        b[cIndex--] = a[aIndex--];
    }
 
    while (bIndex >= 0) {
        b[cIndex--] = b[bIndex--];
    }
 
    return b;
}

Additional array questions are in the String section, since strings are usually represented as arrays of characters.

Webfaction is the ULTIMATE hosting platform for any serious developer.
SSH, WordPress, Rails, Django, cronjobs, compile and execute anything.
ProgrammingInterview.com is proudly powered by Webfaction.