Leetcode: 339. Nested List Weight Sum

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)

Understand the problem:
Because the input is nested, it is natural to think about the problem in a recursive way. We go through the list of nested integers one by one, keeping track of the current depth d. If a nested integer is an integer n, we calculate its sum as n * d. If the nested integer is a list, we calculate the sum of this list recursively using the same process but with depth d+1.

Code (Java):

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) {
            return 0;
        }
        
        return depthSumHelper(nestedList.iterator(), 1);
    }
    
    private int depthSumHelper(Iterator<NestedInteger> iterator, int depth) {
        if (!iterator.hasNext()) {
            return 0;
        }
        
        int sum = 0;
        
        while (iterator.hasNext()) {
            NestedInteger curr = iterator.next();
            if (curr.isInteger()) {
                sum += curr.getInteger() * depth;
            } else {
                sum += depthSumHelper(curr.getList().iterator(), depth + 1);
            }
        }
        
        return sum;
    }
}

Another solution without passing an iterator:

public int depthSum(List<NestedInteger> nestedList) {
    return depthSum(nestedList, 1);
}

public int depthSum(List<NestedInteger> list, int depth) {
    int sum = 0;
    for (NestedInteger n : list) {
        if (n.isInteger()) {
            sum += n.getInteger() * depth;
        } else {
            sum += depthSum(n.getList(), depth + 1);
        }
    }
    return sum;
}

Analysis:

The algorithm takes $O(N)$ time, where $N$ is the total number of nested elements in the input list. For example, the list [ [[[[1]]]], 2 ] contains $4$ nested lists and $2$ nested integers ($1$ and $2$), so $N=6$.

In terms of space, at most $O(D)$ recursive calls are placed on the stack, where $D$ is the maximum level of nesting in the input. For example, $D=2$ for the input [[1,1],2,[1,1]], and $D=3$ for the input [1,[4,[6]]].

Leetcode: House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Understand the problem:
It is a classic DP problem. Define dp[n + 1], where dp[i] means the maximum money till first i houses. 
dp[0] = 0;
dp[1] = nums[1];

dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);

and the final status is dp[n].

Code (Java):

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (nums.length == 1) {
            return nums[0];
        }
        
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        
        int[] dp = new int[nums.length + 1];
        
        dp[0] = 0;
        dp[1] = nums[0];
        
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        
        return dp[nums.length];
    }
}

A constant space solution:
Since now dp[i] only depends on dp[i - 1] and dp[i - 2], we could just use three variables for the DP problem. 

Code (Java):

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (nums.length == 1) {
            return nums[0];
        }
        
        //int[] dp = new int[nums.length + 1];
        
        int dp2 = 0;
        int dp1 = nums[0];
        int max = 0;
        
        for (int i = 2; i <= nums.length; i++) {
            max = Math.max(nums[i - 1] + dp2, dp1);
            dp2 = dp1;
            dp1 = max;
        }
        
        return max;
    }
}

Leetcode: Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Understand the problem:
The problem is very similar to the maximum subarray, which calculates the maximum addition of a subarray. Unlike the in the maximum subarray problem the local optimal can lead to the global optimal, the maximum product subarray cannot. e.g. -2 3 -4, where at -4 the local max is -4, however the global should be -2 * 3 * -4. 

The solution is to maintain to dp arrays, one maintains the local min and the other maintain the local max. Therefore, we define the DP arrays as
dpMin[i], the minimum subarray INCLUDING nums[i]
dpMax[i], the maximum subarray INCLUDING nums[i]

dpMin[i] = Min(dpMin[i - 1] * A[i], dpMax[i - 1] * A[i], A[i]);
dpMax[i] = Max(dpMax[i - 1] * A[i], dp[Min[i - 1] * A[i], A[i]);

The final state is to check max(result, dpMax[i]). 

Code (Java):

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dpMin = new int[len];
        int[] dpMax = new int[len];
        
        dpMin[0] = nums[0];
        dpMax[0] = nums[0];
        
        for (int i = 1; i < len; i++) {
            dpMin[i] = Math.min(Math.min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i]), nums[i]);
            dpMax[i] = Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]);
        }
        
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, dpMax[i]);
        }
        
        return max;
    }
}

A constant space solution:
Note that dp[i] only relies on dp[i - 1], so we could just use two variables to solve the problem. 

Code (Java):

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int min = nums[0];
        int max = nums[0];
        
        int result = nums[0];
        
        for (int i = 1; i < len; i++) {
            
            int curMin = Math.min(Math.min(min * nums[i], max * nums[i]), nums[i]);
            int curMax = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            
            min = curMin;
            max = curMax;
            result = Math.max(result, max);
        }
        
        return result;
    }
}

Follow-up: 
How about the maximum product subsequence? For example, 2 -3 4, the result is 2 * 4 = 8

The solution would be very similar to the maximum product subarray. The only difference is max and min do not necessary include the nums[i]. Therefore, 
min = Min(min, min * nums[i], max * nums[i], nums[i]);
max = Max(max, max * nums[i], min * nums[i], nums[i]);
result = Max(result, max);

Leetcode: Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[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].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Understand the problem:
Note that the problem does not allow to use division and the time complexity should be in O(n). 

One solution is to maintain to arrays, to maintain the product before a[i] and after a[i]. 
i.e, for a[i], we have product of a[0] * a[1] * ... * a[i - 1], and a[n - 1] * ... * a[i + 1]. 
Therefore we can iterate the nums array forward and backward order, respectively.  
And for result[i] = before[i] * after[i].

Code (Java):

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        
        int len = nums.length;
        int[] result = new int[len];
        int[] before = new int[len];
        int[] after = new int[len];
        
        before[0] = 1;
        for (int i = 1; i < len; i++) {
            before[i] = before[i - 1] * nums[i - 1];
        }
        
        after[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            after[i] = after[i + 1] * nums[i + 1];
        }
        
        for (int i = 0; i < len; i++) {
            result[i] = before[i] * after[i];
        }
        
        return result;
    }
}

A constant space solution:
Note the the previous solution requires O(n) space cost. Can we solve the problem by only using constant space? The answer is yes. 

The idea is still the same. The only difference is we do the in-place. First of all, we iterate the nums array in forward and update the partial result. Then iterate the nums array again backward the update the final result. Instead of maintaining a after array, we only need one variable to maintain the after_i. 

Code (Java):

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        
        int[] result = new int[nums.length];
        result[0] = 1;
        
        // before a[i]
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        // after a[i]
        int after = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            result[i] *= after * nums[i + 1];
            after *= nums[i + 1];
        }
        
        return result;
    }
}

Leetcode: Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Understand the problem:
The naive approach is to use a sliding window, with size of 10. Put the visited string into a map. If the substring is visited again, add into the result. 

Code (Java):

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return result;
        }
        
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        int lo = 0;
        int hi = 9;
        
        while (hi < s.length()) {
            String substring = s.substring(lo, hi + 1);
            if (map.containsKey(substring) && map.get(substring) == 1) {
                result.add(substring);
                map.put(substring, map.get(substring) + 1);
            } else {
                map.put(substring, 1);
            }
            
            lo++;
            hi++;
        }
        
        return result;
    }
}

The code got memory limit exceeding error. Why? Because the space complexity is O(10 * n). We need to think of a better approach with less memory cost. 

Use bit manipulation:
Since the string contains only 4 characters, we could encode the characters using 2 bits each, i.e, 
'A' -- 00
'C' -- 01
'G' -- 10
'T'  -- 11
And since the length of the substring is only 10 characters, the total number of bits needed are only 20. Therefore we could encode a string into a integer. 

Code (Java):

public class Solution {
    private Map<Character, Integer> codingMap = new HashMap<Character, Integer>();
    
    private int encode(String s) {
        int value = 0;
        for (int i = 0; i < s.length(); i++) {
            value = (value << 2) + codingMap.get(s.charAt(i));
        }
        
        return value;
    }
    
    private void fill() {
        codingMap.put('A', 0);
        codingMap.put('C', 1);
        codingMap.put('G', 2);
        codingMap.put('T', 3);
    }
    
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return result;
        }
        
        fill();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        int lo = 0;
        int hi = 9;
        
        while (hi < s.length()) {
            String substring = s.substring(lo, hi + 1);
            int hashCode = encode(substring);
            if (map.containsKey(hashCode) && map.get(hashCode) == 1) {
                result.add(substring);
                map.put(hashCode, map.get(hashCode) + 1);
            } else {
                if (!map.containsKey(hashCode)) {
                    map.put(hashCode, 1);
                } else {
                    map.put(hashCode, map.get(hashCode) + 1);
                }
            }
            
            lo++;
            hi++;
        }
        
        return result;
    }
}

Analysis:
Now let's analyze the space cost. Since in Java, each character takes 2 bytes. For the previous solution using string, a 10-character substring takes 20 byte. For using the integer, which takes only 4 bytes. So the new solution saves the memory by 1/5. 

Leetcode: Shortest Word Distance III

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

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

word1 and word2 may be the same and they represent two individual words in the list.

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

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

Note:
You may assume word1 and word2 are both in the list.Understand the problem:

Understand the problem:
The problem is an extension of the previous one. The only diff is the word1 and word2 can be the same. It can still be easily solved by using a hash map. The question is, can we solve it by using the one-pass of the array? 

The key is we cannot update the two pointers simultaneously, if they are the same. We could update one, compare the distance, and then update the other. 

Code (Java):

public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int posA = -1;
        int posB = -1;
        int minDistance = Integer.MAX_VALUE;
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            
            if (word.equals(word1)) {
                posA = i;
            } else if (word.equals(word2)) {
                posB = i;
            }
            
            if (posA != -1 && posB != -1 && posA != posB) {
                minDistance = Math.min(minDistance, Math.abs(posA - posB));
            }
            
            if (word1.equals(word2)) {
                posB = posA;
            }
        }
        
        return minDistance;
    }
}

Leetcode: 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.

Understand the problem:
The problem can be solved by one-pass of the array. 
Iterate through the array, use two pointers pointing to the index of the word1 and word2, maintain the minimum distance. 

Code (Java):

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int posA = -1;
        int posB = -1;
        
        int minDistance = Integer.MAX_VALUE;
        
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                posA = i;
            }
            
            if (words[i].equals(word2)) {
                posB = i;
            }
            
            if (posA != -1 && posB != -1) {
                minDistance = Math.min(minDistance, Math.abs(posA - posB));
            }
        }
        
        return minDistance;
    }
}

Leetcode: Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Understand the problem:
The problem asks for designing a class TwoSum which supports two operations, add and find. There are two data structures / design decisions to think about. 
 1. Use two pointers. Requires the list to be sorted. 
       -- add: insert an element to a sorted array requires O(logn) + O(n) time. 
       -- find: use two pointers. Takes O(n) time. 

2. Use a hash map. 
       -- Add takes O(1) time. 
       -- Find takes O(n) time. 

Note that we have to use  the map instead of the set because we need to counter the number of duplicates for a number. e.g. add(0), add(0) and find(0). 

Code (Java):

public class TwoSum {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
 public void add(int number) {
     if (map.containsKey(number)) {
         int val = map.get(number) + 1;
         map.put(number, val);
     } else {
         map.put(number, 1);
     }
 }

 public boolean find(int value) {
     if (map.isEmpty()) {
         return false;
     }
     Iterator it = map.entrySet().iterator();

     // Itearte over the set
     while (it.hasNext()) {
         Map.Entry pair = (Map.Entry) it.next();
         int firstKey =  (int) pair.getKey();
         int firstValue = (int) pair.getValue();
         
         int secondKey = value - firstKey;
         
         // 0 + 0 = 0
         if (firstKey == secondKey && firstValue >= 2) {
             return true;
         }  else if (firstKey != secondKey && map.containsKey(secondKey)) {
             return true;
         }
     }
     return false;
 }
}

Follow-up: 
What if you add a few, but search very heavily? You need to make sure search only takes O(1) time. Add(num), add num with all the previous added numbers 
search(target), only takes O(1) time. 

Code (Java)

public class FasterSearchSum implements TwoSum {
    Set<Integer> set = new HashSet<>();
    List<Integer> nums = new ArrayList<>();
    
    public void store(int input) {
        if (!nums.isEmpty()) {
            for (int num : nums) {
                set.add(input + num);
            }
        }
        
        nums.add(input);
    }
    
    public boolean test(int val) {
        return set.contains(val);
    }
}

Leetcode: Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Understand the problem:
The problem gives a sorted array which is rotated at some pivot, search for a target value. This problem clearly indicates that we do find the number in O(logn) time, just as binary search. 

One naive idea is to find the pivot and rotate the array back, then we can apply the binary search. But rotating the array would take on average O(n) time, which is not allowed in this problem. 

Solution:
The solution is very similar to binary search. Note that no matter how we rotated the array, there must be at least one part which is sorted. If the target is at the sorted part, we just search that part until we found; else we go the unsorted part. 

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

Discussion:
Now let's analyze the complexity. If the target just falls into the sorted part, the complexity could be O(logn). How about the worst case, where target is always not in the sorted part, then we have to iterate all the data of the array, then the complexity becomes O(n). So on average, we can see that the complexity is O(logn).

Summary:
This is an extension of the binary search. So it is very important that you got familiar with the binary search. 

Update on 9/29/14:

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else {
                if (A[mid] < target && target <= A[hi] ) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
        }
        
        if (target == A[lo]) {
            return lo;
        }
        
        if (target == A[hi]) {
            return hi;
        }
        
        return -1;
        
    }
}

Update on 7/13/18:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int ans = -1;
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else {
                // case 1: left half is sorted
                //
                if (nums[lo] < nums[mid]) {
                    if (target >= nums[lo] && target < nums[mid]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else if (nums[mid] < nums[hi]) {
                    if (target > nums[mid] && target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
        }
        
        if (nums[lo] == target) {
            return lo;
        }
        
        if (nums[hi] == target) {
            return hi;
        }
        
        return -1;
    }
}