LeetCode – Page 3 – programmingpuzzles

Posted on May 9, 2019May 9, 2019 by seeker

LeetCode – 31 : Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

[code lang="java"]
class Solution {
    public void nextPermutation(int[] nums) {
        
    }
}
[code]

Idea – 1

Idea is to increase the sequence as little as possible. We index from right to left (lsb to msb). Smallest increase is achieved by swapping two elements $a_i$ and $a_j$ such that $i > j$ and $a_i < a_j$ and $a_j$ is the smallest such number in [i-1..0]. After swapping we decrease [i-1..0] as much as possible. For example, in [1, 2, 4, 3], from right to left since [4, 3] is non-decreasing, we cannot find $a_i$ and $a_j$ that meet the requirements. However, 2 is the best candidate for $a_i$ since anything left of 2 will make the increase bigger. The smallest number bigger than 2 and right of 2 is 3, so we swap 2 and 3 and get [1, 3, 4, 2]. Now we decrease right of 3 as much as possible by just reversing it, since right of 3 is guaranteed to be nondecreasing (right to left). Finally we have the next higher permutation [1, 3, 2, 4]. Time complexity is $O(n)$ and space complexity is $O(1)$ .

[code lang="java"]
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while(i >= 0)
        {
            if(nums[i] < nums[i+1])
            {
                break;
            }
            
            --i;
        }
        
        if(i < 0) // highest permutation, cannot increase
        {
            reverse(nums, 0, n-1);
            return;
        }
        
        int j = n-1;
        while(j > i)
        {
            if(nums[j] > nums[i])
            {
                break;
            }
            
            --j;
        }
        
        swap(nums, i, j);
        reverse(nums, i+1, n-1);
    }
    
    private void reverse(int[] A, int begin, int end)
    {
        while(begin < end)
        {
            swap(A, begin++, end--);
        }
    }
    
    private void swap(int[] A, int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
[code]

Runtime: 1 ms, faster than 99.58% of Java online submissions for Next Permutation.Memory Usage: 37.2 MB, less than 94.57% of Java online submissions for Next Permutation.

Posted on May 8, 2019May 8, 2019 by seeker

LeetCode – 22 : Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

[code lang="java"]
class Solution {
    public List<String> generateParenthesis(int n) {

    }
}
[code]

Idea – 1

If there is an open parenthesis left to take, we take it. If there is a close parenthesis left to take and taking it would not make close count bigger than open count, we take it. Time and space complexity both are proportional to Catalan number (exponential).

[code lang="java"]
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        collect(n, 0, 0, "", ans);
        
        return ans;
    }
    
    private void collect(int n, int openused, int closeused, String current, List<String> result)
    {
        if(openused==n && closeused==n)
        {
            result.add(current);
            return;
        }
        
        if(openused < n)
        {
            collect(n, openused+1, closeused, current+"(", result);
        }
        
        if(closeused < openused)
        {
            collect(n, openused, closeused+1, current+")", result);
        }
    }
}
[code]

Runtime: 1 ms, faster than 96.17% of Java online submissions for Generate Parentheses.Memory Usage: 35.2 MB, less than 100.00% of Java online submissions for Generate Parentheses.

Posted on May 7, 2019May 7, 2019 by seeker

LeetCode – 811 : Subdomain Visit Count

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

Example 1: 
Input:  ["9001 discuss.leetcode.com"] 
Output:  ["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"] 
Explanation:  We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2: 
Input:  ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"] 
Output:  ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"] 
Explanation:  We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 “.” characters.
The input count in any count-paired domain will not exceed 10000.
The answer output can be returned in any order.

Idea – 1

We break each cpdomain into count and domain. Then in the domain part we process from right to left since all higher level domain has the same count. Since dot count and lengths are limited, this has time and space $O(n)$ .

[code lang="java"]
class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> ans = new ArrayList<>();
        if(cpdomains==null || cpdomains.length==0)
        {
            return ans;
        }
        
        int n = cpdomains.length;
        
        HashMap<String, Integer> map = new HashMap<>();
        for(String cp : cpdomains)
        {
            String[] pair = cp.split(" ");
            int count =  Integer.parseInt(pair[0]);
            
            String[] parts = pair[1].split("\\.");
            
            String prev = "";
            for(int i = parts.length-1; i >= 0; --i)
            {
                String key = parts[i];
                if(!prev.isEmpty())
                {
                    key = key+"."+prev;
                }
                
                int oldCount = map.getOrDefault(key, 0);
                map.put(key, oldCount + count);
                
                prev = key;
            }
        }
        
        for(String k : map.keySet())
        {   
            int count =  map.get(k);
            ans.add( String.format("%d %s", count, k) );
        }
        
        return ans;
    }
}
[code]

Runtime: 36 ms, faster than 12.47% of Java online submissions for Subdomain Visit Count.Memory Usage: 39.6 MB, less than 48.68% of Java online submissions for Subdomain Visit Count.

Posted on May 4, 2019 by seeker

LeetCode – 322: Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11 
Output: 3  
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3 
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
    }
}
[code]

Idea – 1

Starting with the first coin we try taking it once, twice etc., for each such choice we try taking second coin once, twice, etc. If the smallest coin goes into amount m number of times and there are n coins, time complexity is $O(n^m)$ and space complexity due to recursion stack is $O(n)$ .

[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = dfs(coins, 0, amount);
        
        return n == Integer.MAX_VALUE ? -1 : n;
    }
    
    private int dfs(int[] coins, int i, int amount)
    {
        if(i >= coins.length || amount < 0)
        {
            return Integer.MAX_VALUE;
        }
        
        if(amount == 0) // found a change
        {
            return 0;
        }
        
        int takeit = dfs(coins, i, amount-coins[i]);
        if(takeit < Integer.MAX_VALUE)
        {
            // take into account the current coin
            ++takeit;
        }
        
        int leaveit = dfs(coins, i+1, amount);
        
        return Math.min(takeit, leaveit);
    }
}
[code]

Time limit exceeded for the following input:

[122,112,383,404,25,368]
6977

Idea – 2

Looking at dfs(), it has two params of interest i and amount, so there are only n*amount number of distinct calls. We shall cache. Time complexity is $O(n\cdot \textrm{amount})$ and space complexity is also $O(n\cdot \textrm{amount})$ .

[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
        if(coins.length == 0)
        {
            return -1;
        }
        
        Integer[][] cache = new Integer[coins.length][amount+1];
        
        int n = dfs(coins, 0, amount, cache);
        
        return n == Integer.MAX_VALUE ? -1 : n;
    }
    
    private int dfs(int[] coins, int i, int amount, Integer[][] cache)
    {
        if(i >= coins.length || amount < 0)
        {
            return Integer.MAX_VALUE;
        }
        
        if(amount == 0) // found a change
        {
            return 0;
        }
        
        if(cache[i][amount] != null)
        {
            return cache[i][amount];
        }
        
        int takeit = dfs(coins, i, amount-coins[i], cache);
        if(takeit < Integer.MAX_VALUE)
        {
            // take into account the current coin
            ++takeit;
        }
        
        int leaveit = dfs(coins, i+1, amount, cache);
        
        cache[i][amount] = Math.min(takeit, leaveit);
        
        return cache[i][amount];
    }
}
[code]

Runtime: 41 ms, faster than 12.06% of Java online submissions for Coin Change.
Memory Usage: 38.3 MB, less than 10.49% of Java online submissions for Coin Change.

Idea – 3

Bottom up dynamic programming, time and space $O(n\cdot \textrm{amount})$ .

[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
        if(coins.length == 0)
        {
            return -1;
        }
        
        int n = coins.length;
        
        int[][] dp = new int[n][amount+1];
        for(int a = 1; a <= amount; ++a)
        {
            dp[0][a] = (a%coins[0]==0) ? a/coins[0] : Integer.MAX_VALUE;
        }
        
        for(int i = 0; i < n; ++i)
        {
            dp[i][0] = 0;
        }
        
        for(int i = 1; i < n; ++i)
        {
            for(int a = 1; a <= amount; ++a)
            {
                // if taking current coin makes sense
                int takeit = (coins[i] <= a && dp[i][a-coins[i]] != Integer.MAX_VALUE) ? 1+dp[i][a-coins[i]] : Integer.MAX_VALUE;
                int leaveit = dp[i-1][a];
                
                dp[i][a] = Math.min(takeit, leaveit);
            }
        }
        
        return dp[n-1][amount] == Integer.MAX_VALUE ? -1 : dp[n-1][amount];
    }
}
[code]

Runtime: 13 ms, faster than 78.26% of Java online submissions for Coin Change.
Memory Usage: 37.5 MB, less than 90.66% of Java online submissions for Coin Change.

Idea – 4

To update dp[i][a], we need either dp[i-1][a] or dp[i][a-coins[i]], so keeping a single row is enough. Thus time remains $O(n\cdot \textrm{amount})$ , but space becomes $O(\textrm{amount})$ .

[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
        if(coins.length == 0)
        {
            return -1;
        }
        
        int n = coins.length;
        
        int[] dp = new int[amount+1];
        
        // 0-th coin
        for(int a = 1; a <= amount; ++a)
        {
            dp[a] = (a%coins[0]==0) ? a/coins[0] : Integer.MAX_VALUE;
        }
        
        for(int i = 1; i < n; ++i)
        {
            for(int a = 1; a <= amount; ++a)
            {
                // if taking current coin makes sense
                int takeit = (coins[i] <= a && dp[a-coins[i]] != Integer.MAX_VALUE) ? 1+dp[a-coins[i]] : Integer.MAX_VALUE;
                int leaveit = dp[a];
                
                dp[a] = Math.min(takeit, leaveit);
            }
        }
        
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
[code]

Runtime: 11 ms, faster than 84.75% of Java online submissions for Coin Change.
Memory Usage: 37 MB, less than 93.91% of Java online submissions for Coin Change.

Posted on May 3, 2019May 3, 2019 by seeker

LeetCode – 33 : Search in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 
Output: -1

[code lang="java"]
class Solution {
    public int search(int[] nums, int target) {
        
    }
}
[code]

Idea – 1

There are no duplicates. So, after rotation the single sorted array breaks into two sorted arrays separated by a break. We do modified binary search, deciding to go left or right but we need to consider cases when mid is to the left or to the right of the break. Time complexity is $O(\lg{n})$ and space is $O(1)$ .

[code lang="java"]
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        while(lo <= hi)
        {
            int mid = lo + (hi-lo)/2;
            
            if(target == nums[mid])
            {
                return mid;
            }
            else if(nums[mid] > nums[hi]) // mid is to the left of break
            {
                if(target >= nums[lo] && target < nums[mid]) // target is between lo and mid
                {
                    // go left
                    hi = mid-1;
                }
                else
                {
                    // go right
                    lo = mid+1;
                }
            }
            else // mid is to the right of break;
            {
                if(target > nums[mid] && target <= nums[hi]) // target is between mid and hi
                {
                    // go right
                    lo = mid+1;
                }
                else
                {
                    // go left
                    hi = mid-1;
                }
            }
        }
        
        return -1;
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 38.9 MB, less than 75.56% of Java online submissions for Search in Rotated Sorted Array.

Posted on April 8, 2019April 8, 2019 by seeker

LeetCode-1: Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea – 1

Try each of the $O(n^2)$ pairs and see if the sum equals target.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] sol = new int[2];
        for(int i = 0; i < nums.length-1; ++i)
        {
            for(int j = i+1; j < nums.length; ++j)
            {
                int sum = nums[i]+nums[j];
                if(sum==target)
                {
                    sol[0] = i;
                    sol[1] = j;
                    
                    return sol;
                }
            }
        }
        
        return sol;
    }
}

Runtime: 22 ms, faster than 29.76% of Java online submissions for Two Sum. Memory Usage: 38.4 MB, less than 52.20% of Java online submissions for Two Sum.

Idea – 2

For i-th element x, find target-x and see if we have already seen it in [0, i-1]. For efficient lookup we use a HashMap that stores the last index where an element was seen. Time and space $O(n)$ . Overflow/underflow does not seem to create an issue in Java probably because the addition and subtraction behaves like being on a circle.

		int target = Integer.MIN_VALUE;
		int x = 1000;
		int y = target-x;
		int z = x+y;
		
		System.out.println( String.format( "x=%d, y=%d, z=%d", x, y, z ) );
		
		target = Integer.MAX_VALUE;
		x = -1000;
		y = target-x;
		z = x+y;
		
		System.out.println( String.format( "x=%d, y=%d, z=%d", x, y, z ) );

x=1000, y=2147482648, z=-2147483648

x=-1000, y=-2147482649, z=2147483647

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] sol = new int[2];
        HashMap<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; ++i)
        {
            int delta = target-nums[i];
            if(map.containsKey(delta))
            {
                sol[0] = map.get(delta);
                sol[1] = i;
                break;
            }
            
            map.put(nums[i], i);
        }
        
        return sol;
    }
}

Runtime: 2 ms, faster than 99.73% of Java online submissions for Two Sum. Memory Usage: 38 MB, less than 84.34% of Java online submissions for Two Sum.