Posted on by seeker

LeetCode – 412 : Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

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

Idea – 1

Iterate from 1 through n, check different conditions. Time complexity is linear. Space complexity constant (ignoring output size). 
[code lang="java"]
class Solution {
    
    public List<String> fizzBuzz(int n) {
        List<String> ans = new ArrayList<>();
        if(n < 1)
        {
            return ans;    
        }
        
        for(int x = 1; x <= n; ++x)
        {
            if(x%15 == 0)
            {
                ans.add("FizzBuzz");
            }
            else if(x%3 == 0)
            {
                ans.add("Fizz");
            }
            else if(x%5 == 0)
            {
                ans.add("Buzz");
            }
            else
            {
                ans.add(String.valueOf(x));
            }
        }
        
        return ans;
    }
}
[code]

Runtime: 1 ms, faster than 100.00% of Java online submissions for Fizz Buzz.Memory Usage: 36.2 MB, less than 99.97% of Java online submissions for Fizz Buzz.

Posted on by seeker

LeetCode – 9 : Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

[code lang="java"]
class Solution {
    public boolean isPalindrome(int x) {
        
    }
}
[code]

Idea – 1

If a number has a negative sign, it cannot be a palindrome number. Otherwise, we match digits from the two ends. Time complexity is O\left(\log_{10} n\right) and space complexity is O(1). 
[code lang="java"]
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0)
        {
            return false;
        }
        
        // single digit is palindrome
        if(x < 10)
        {
            return true;
        }
        
        int j = (int)Math.log10(x);
        int i = 0;
        
        while(i < j)
        {
            if(getDigit(x, i++) != getDigit(x, j--))
            {
                return false;
            }
        }
        
        return true;
    }
    
    private int getDigit(int x, int i)
    {
       int msbExponent = (int)Math.log10(x);    
       int msbPower = (int)Math.pow(10, msbExponent);
        
       if(i == msbExponent)
       {
           return x/msbPower;
       }
        
       int MOD = (int)Math.pow(10, i+1);
       int ans = x%MOD;
       int DIV = (int)Math.pow(10, i);
       ans /= DIV;
        
       return ans;
    }
}
[code]

Runtime: 27 ms, faster than 57.69% of Java online submissions for Palindrome Number.Memory Usage: 34.9 MB, less than 80.99% of Java online submissions for Palindrome Number.

Posted on by seeker

LeetCode – 54 : Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
[code lang="java"]
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
    }
}
[code]

Idea – 1

Spiral pattern goes layer by layer – from outer layer towards inner layer.
We go n places rightwards, we go m-1 one places downwards, we go n-1 places leftwards, and m-2 places upwards – that ends one layer. We keep processing layers in this way until either n or m for a layer becomes zero, which means no more layers to process. Time complexity O(m\cdot n). Excluding output, space complexity O(1). 
[code lang="java"]
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if(matrix == null)
        {
            return ans;
        }
        
        int m = matrix.length;
        if(m == 0)
        {
            return ans;
        }
        
        int n = matrix[0].length;
        
        // we are entering the matrix from left
        int i = 0, j = -1;
        while(n > 0)
        {
            // go n places rightwards
            for(int k = 0; k < n; ++k)
            {
                ans.add(matrix[i][++j]);
            }
            
            --m;
            if(m == 0)
            {
                break;
            }
            
            // go m-1 places downwards
            for(int k = 0; k < m; ++k)
            {
                ans.add(matrix[++i][j]);
            }
            
            --n;
            if(n == 0)
            {
                break;
            }
            
            // go n-1 places leftwards
            for(int k = 0; k < n; ++k)
            {
                ans.add(matrix[i][--j]);
            }
            
            --m;
            if(m == 0)
            {
                break;
            }
            
            // go m-2 places upwards
            for(int k = 0; k < m; ++k)
            {
                ans.add(matrix[--i][j]);
            }
            
            // prepare n for next layer
            --n;
        }
        
        return ans;
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Spiral Matrix.Memory Usage: 33.5 MB, less than 100.00% of Java online submissions for Spiral Matrix.

Posted on by seeker

LeetCode – 46 : Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
[code lang="java"]
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
    }
}
[code]

Idea – 1

With n distinct numbers, there are n! distinct permutations. We shall do dfs, first level has n choices, second level has n-1 choices, so on. Any solution has time complexity O(n\cdot n!). Output has size O(n\cdot n!). Additional space complexity is O(n). 
[code lang="java"]
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums==null || nums.length==0)
        {
            return result;
        }
        
        boolean[] visited = new boolean[nums.length];
        
        collect(nums, visited, new LinkedList<Integer>(), result);
        
        return result;
    }
    
    private void collect(int[] nums, boolean[] visited, LinkedList<Integer> buffer, List<List<Integer>> result)
    {
        if(buffer.size() == nums.length)
        {
            result.add(new ArrayList<>(buffer));
            return;
        }
        
        for(int i = 0; i < visited.length; ++i)
        {
            if(!visited[i])
            {
                visited[i] = true;
                buffer.addLast(nums[i]);
                collect(nums, visited, buffer, result);
                buffer.removeLast();
                visited[i] = false;
            }
        }
    }
}
[code]

Runtime: 1 ms, faster than 99.75% of Java online submissions for Permutations.Memory Usage: 36.6 MB, less than 96.01% of Java online submissions for Permutations.

Posted on by seeker

LeetCode – 215 : Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: 
You may assume k is always valid, 1 ≤ k ≤ array’s length.

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

Idea – 1

Sort in non-increasing order and return the k-th element. Time and space complexity are that of a comparison based sorting. With traditional mergesort time is O(n\lg{n}) ans space is be O(n). With quicksort average time is O(n\lg{n}) and average space is O(lg{n}). With heapsort time is O(n\lg{n}) and space is O(1). 
[code lang="java"]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        Integer[] boxedArray = new Integer[n];
        for(int i = 0; i < n; ++i)
        {
            boxedArray[i] = nums[i];
        }
        
        Arrays.sort(boxedArray, (a, b) -> (b - a));
        
        return boxedArray[k-1];
    }
}
[code]

Runtime: 41 ms, faster than 11.26% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 38 MB, less than 62.44% of Java online submissions for Kth Largest Element in an Array.

Idea – 2

We use quickselect: repeatedly partition the array around a random pivot and go right or left based on the rank of the pivot. Average time O(n) and average space O(\lg{n}). Worst case time is O(n^2) and worst case space is O(n). 
[code lang="java"]
class Solution {
    
    private static final Random rng = new Random(System.currentTimeMillis() % Integer.MAX_VALUE);
    
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        return partition(nums, 0, n-1, k);
    }
    
    private void swap(int[] A, int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
    
    private int partition(int[] A, int lo, int hi, int k)
    {
        int z = lo+rng.nextInt(hi-lo+1);
        int pivot = A[z];
        int i = lo-1, x = lo, j = hi;
        while(x <= j)
        {
            if(A[x] < pivot)
            {
                swap(A, ++i, x++);
            }
            else if(A[x] > pivot)
            {
                swap(A, x, j--);
            }
            else
            {
                ++x;
            }
        }
        
        // (i+1) is where pivot is right now
        int rank = A.length-(i+1);
        
        if(rank==k)
        {
            return pivot;
        }
        else if(rank < k)
        {
            return partition(A, lo, i, k);
        }
        else
        {
            return partition(A, i+2, hi, k);
        }
    }
}
[code]

Runtime: 1 ms, faster than 99.81% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 35.6 MB, less than 97.57% of Java online submissions for Kth Largest Element in an Array.

Posted on by seeker

LeetCode – 13 : Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is notIIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9. 
  • X can be placed before L (50) and C (100) to make 40 and 90. 
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
[code lang="java"]
class Solution {
    public int romanToInt(String s) {
        
    }
}
[code]

Idea – 1

If next numeral is bigger we subtract current numeral from the total, otherwise we add the current numeral. Time is O(n) and space is O(1). 
[code lang="java"]
class Solution {
    
    private HashMap<Character, Integer> map;
    
    public Solution()
    {
        map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
    }
    
    public int romanToInt(String s) {
        int n = s.length();
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int currVal = map.get(s.charAt(i));
            if(i < n-1)
            {
                int nextVal = map.get(s.charAt(i+1));
                if(currVal < nextVal)
                {
                    // we always add currVal, so this is effectively ans -= currVal
                    ans -= 2*currVal;
                }
            }
            
            ans += currVal;
        }
        
        return ans;
    }
}
[code]

Runtime: 6 ms, faster than 77.23% of Java online submissions for Roman to Integer.Memory Usage: 35.6 MB, less than 99.98% of Java online submissions for Roman to Integer.

Posted on by seeker

LeetCode – 380 : Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
[code lang="java"]
class RandomizedSet {

    /** Initialize your data structure here. */
    public RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
[code]

Idea – 1

It is easy to make insert/remove O(1) using a hash-based data structure. From n elements, to drant at random, we choose a random id between [0..n-1] and get the corresponding element. Since given an id we need to find the element in O(1) time, we need hash map from id to element. Since we insert/remove elements (not ids), we need another hash map from element to its id. When we remove an element, we find its id and swap with the element with largest id (we need to update the element-to-id map for the element with largest id), then first remove the largest id from id-to-element map, and then remove the element from element-to-id map. 
[code lang="java"]
class RandomizedSet {
    
    private HashMap<Integer, Integer> elementToIdMap;
    private HashMap<Integer, Integer> idToElementMap;
    private static final Random rng = new Random(System.currentTimeMillis()%Integer.MAX_VALUE); 

    /** Initialize your data structure here. */
    public RandomizedSet() {
        elementToIdMap = new HashMap<>();
        idToElementMap = new HashMap<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        boolean exists = elementToIdMap.containsKey(val);
        
        if(!exists)
        {
            int id = elementToIdMap.size();
            elementToIdMap.put(val, id);
            idToElementMap.put(id, val);
        }
        
        return !exists;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        boolean exists = elementToIdMap.containsKey(val);
        
        if(exists)
        {
            int maxIdElement = idToElementMap.get(elementToIdMap.size()-1);
            int id = elementToIdMap.get(val);
            
            idToElementMap.put(id, maxIdElement);
            elementToIdMap.put(maxIdElement, id);
            
            idToElementMap.remove(elementToIdMap.size()-1);
            elementToIdMap.remove(val);
        }
        
        return exists;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int n = elementToIdMap.size();
        int draw = rng.nextInt(n);
        return idToElementMap.get(draw);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
[code]

Runtime: 57 ms, faster than 54.30% of Java online submissions for Insert Delete GetRandom O(1).Memory Usage: 46.5 MB, less than 80.37% of Java online submissions for Insert Delete GetRandom O(1).

Posted on by seeker

LeetCode – 79 : Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
[code lang="java"]
class Solution {
    public boolean exist(char[][] board, String word) {

    }
}
[code]

Idea – 1

We do dfs once from every cell of the board. A cell would stay ‘visited’ only for the fours sub-dfses from its four neighbors, otherwise we remove the cell from ‘visited’ list, this is to allow some other path to use this cell. Consider below, during dfs from cell x, we first visit its right neighbor cell y. All 4 neighbors of cell y fail to find a match, do we now keep cell y marked as ‘visited’?
No. Because there could be a legitimate path from x through x’s bottom neighbor and that path may require cell y like below:
Since the graph has 4\cdot n edges, we ignore edge count in the complexity. We are doing n dfs’es, time complexity is O(n^2) and since we are doing a single dfs any one time space complexity is O(n). 
[code lang="java"]
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board==null)
        {
            return false;
        }
        
        if(board.length==0)
        {
            return word.isEmpty();
        }
        
        int m = board.length;
        int n = board[0].length;
        
        for(int row = 0; row < m; ++row)
        {
            for(int col = 0; col < n; ++col)
            {
                if(dfs(board, row, col, word, 0))
                {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, int row, int col, String word, int i)
    {
        if(i >= word.length())
        {
            return true;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        if(row < 0 || row >= m || col < 0 || col >= n || board[row][col] == '*' || word.charAt(i) != board[row][col])
        {
            return false;
        }
        
        char old = board[row][col];
        board[row][col] = '*';
        
        boolean found = 
               dfs(board, row-1, col, word, i+1) 
            || dfs(board, row, col+1, word, i+1) 
            || dfs(board, row+1, col, word, i+1) 
            || dfs(board, row, col-1, word, i+1);
        
        board[row][col] = old;
        
        return found;
    }
}
[code]

Runtime: 4 ms, faster than 93.95% of Java online submissions for Word Search.Memory Usage: 37.4 MB, less than 96.83% of Java online submissions for Word Search.

Posted on by seeker

LeetCode – 560 : Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Idea – 1

Try all of the possible O(n^2) subarrays, time O(n^2) and space O(1). 
[code lang="java"]
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        
        for(int i = 0; i < n; ++i)
        {
            int sum = 0;
            for(int j = i; j < n; ++j)
            {
                sum += nums[j];
                if(sum==k)
                {
                    ++count;
                }
            }
        }
        
        return count;
    }
}
[code]

Runtime: 117 ms, faster than 28.52% of Java online submissions for Subarray Sum Equals K.Memory Usage: 38.2 MB, less than 95.55% of Java online submissions for Subarray Sum Equals K.

Idea – 2

If we needed to find two numbers that sum to K, we would be using a hash table. In a similar spirit, the problem could be thought of as finding two cumsums whose difference is k. Therefore if we have two indices p and q (p < q) and \sum_{i=0}^{i=q}\ -\ \sum_{i=0}^{i=p}\ =\ k, then we have a subarray between p and q that sums to K. We could do it in linear time and linear space, compared to first idea, this boils down to a space-time trade-off. 
[code lang="java"]
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // Cumsum(0..j) == K case
        map.put(0, 1);
        
        // cumulative sum
        int cumsum = 0;
        for(int x : nums)
        {
            cumsum += x;
            int delta = cumsum-k;
            
            count += map.getOrDefault(delta, 0);
            
            map.put( cumsum, map.getOrDefault(cumsum, 0)+1 );
        }
        
        
        return count;
    }
}
[code]

Runtime: 14 ms, faster than 85.19% of Java online submissions for Subarray Sum Equals K.Memory Usage: 36.8 MB, less than 98.65% of Java online submissions for Subarray Sum Equals K.

Posted on by seeker

LeetCode – 49 : Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.
[code lang="java"]
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
    }
}
[code]

Idea – 1

Sorted version of a group of anagrams is unique, so we shall use a hashmap to group the anagrams where key will be the sorted version. Since all strings consist of lowercase letters only, we use counting sort to perform sorting in O(m) time – m is number of chars in the longest string. Time complexity is then O(n\cdot m) and space complexity is also O(n\cdot m). 
[code lang="java"]
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if(strs==null || strs.length==0)
        {
            return ans;
        }
        
        HashMap<String, List<String>> map = new HashMap<>();
        for(String w : strs)
        {
            // 26 unique chars
            char[] counts = new char[26];
            for(int i = 0; i < w.length(); ++i)
            {
                ++counts[ w.charAt(i)-'a' ];
            }
            
            String sorted = new String(counts);
            List<String> group = map.getOrDefault(sorted, new ArrayList<>());
            group.add(w);
            
            map.put(sorted, group);
        }
        
        for(String key : map.keySet())
        {
            ans.add(map.get(key));
        }
        
        return ans;
    }
}
[code]

Runtime: 9 ms, faster than 89.34% of Java online submissions for Group Anagrams.Memory Usage: 40.7 MB, less than 93.53% of Java online submissions for Group Anagrams.