Array Traversal

Shortest Word Distance

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.

Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution:

Here is a naive solution:

def shortestDistance(words, word1, word2):
    word1_indices, word2_indices = [], []
    for i, word in enumerate(words):
        if word == word1:
            word1_indices.append(i)
        elif word == word2:
            word2_indices.append(i)
    return min(abs(x-y) for x in word1_indices for y in word2_indices)

Implementation Details

In the above implementation, replacing word1_indices, word2_indices = [], [] with word1_indices = word2_indices = [] will result in a bug.

Both min(abs(x-y) for x in word1_indices for y in word2_indices) and min([abs(x-y) for x in word1_indices for y in word2_indices]) will work but the former is less expensive by using the generator pattern.

Since this implementation does not consider the ordering of word1_indices and word2_indices, we can use sets to store the indices of word1 and word2 instead of using lists.

Time Complexity

It's very easy to think that the run time of the implementation is O(n^2) where n = len(words). This overlooks the fact that comparing strings is not an O(1) operation. So the correct run time is O(kn^2) where k = max(len(word1), len(word2)). (Why not the length of the longest word in words?)

Can we do better?

YES! We do not need to compare every singles pair of x (in word1_indices) and y (in word2_indices) in order to get the smallest distance. An optimized solution can be found in the section on two pointers.

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that result[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Solution:

The core of this question is to find nums[0]*nums[1]*...*nums[i-1]*nums[i+1]*nums[i+2]*...*nums[l-1] where l = len(nums) for each 0≤i<l. This can be accomplished by first traversing nums from left to right, finding nums[0]*nums[1]*...*nums[i-1] and then traversing nums from right to left, finding nums[l-1]*nums[l-2]*...*nums[i+1]. The following implementation illustrates this idea:

def product_except_self(nums):
    nums_length = len(nums)
    product_from_left, product_from_right = [1] * nums_length, [1] * nums_length
    for i in xrange(1, nums_length):
        product_from_left[i] = nums[i-1] * product_from_left[i-1]
    for j in xrange(nums_length-2, -1, -1):
        product_from_right[j] = nums[j+1] * product_from_right[j+1]
    result = [x * y for x, y in zip(product_from_left, product_from_right)]
    return result

The above implementation of product_except_self uses O(2n) extra space to store product_from_left and product_from_right. These two lists are only there to help construct result, can we find a way to construct result using less space?

The implementation below eliminates product_from_left:

def product_except_self_better(nums):
    nums_length = len(nums)
    result, product_from_right = [1] * nums_length, [1] * nums_length
    for i in xrange(1, nums_length):
        result[i] = nums[i-1] * result[i-1]
    for j in xrange(nums_length-2, -1, -1):
        product_from_right[j] = nums[j+1] * product_from_right[j+1]
        result[j] *= product_from_right[j]
    return result

When scanning nums from right to left, we find result[j] by multiplying result[j] with product_from_right[j]. Since product_from_right[j] relies on product_from_right[j+1] we only need the previous product_from_right[j+1] as opposed to the entire array. Hence the following:

def product_except_self_optimized(nums):
    nums_length = len(nums)
    result = [1] * nums_length
    product_from_right = 1
    for i in xrange(1, nums_length):
        result[i] = nums[i-1] * result[i-1]
    for j in xrange(nums_length-2, -1, -1):
        product_from_right *= nums[j+1]
        result[j] *= product_from_right
    return result

Eureka! We manage to find result using only O(1) extra space.

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Solution:

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

For example, given input array nums = [1,1,2], your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Solution:

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Solution: