Buttercola: July 2018

Saturday, July 28, 2018

Leetcode 878. Nth Magical Number

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: N = 1, A = 2, B = 3
Output: 2

Example 2:

Input: N = 4, A = 2, B = 3
Output: 6

Example 3:

Input: N = 5, A = 2, B = 4
Output: 10

Example 4:

Input: N = 3, A = 6, B = 4
Output: 8

Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

Code (Java):

class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        long lo = 2;
        long hi = Long.MAX_VALUE;
         
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
             
            long lcm = A * B / gcd(A, B);
             
            long count = mid / A + mid / B - mid / lcm;
             
            if (count < N) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
         
        long module = (long) Math.pow(10, 9) + 7;
        return (int)(lo % module);
    }
     
    private long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
         
        return gcd(b, a % b);
    }
}

Leetcode 381. Insert Delete GetRandom O(1) - Duplicates allowed

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

Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

A wrong solution:

The problem is similar to the last one, but allows to keep duplicates. So a naive idea is to use Map<Integer, List<Integer>> to store the value and the list of the locations of the value. But why does this solution not work?

For the solution above, we assume that the indices stored in the map are always in an ascending order. So if we swap the value to be deleted, we assume that the list.get(size() - 1) is the tail element of the array. But that's not true. let's take one example:

Insert [1, 1, 2, 2, 3, 3]

Now the hash map is like:

1 -> [0 ,1]

2 -> [2, 3]

3 -> [4, 5]

Remove(2)

After remove, the hash map becomes

1->[0, 1]

2->[2]

3 ->[4, 3]

The array is now:

[1, 1, 2, 3, 3]

Then you remove another 2

Remove(2)

So the hash map becomes

1->[0, 1]

2->[]

3->[4, 2]

The array is now

[1, 1, 3, 3]

See the problem? We thought the tail is index 3, however it should be 4.

So the real problem of using arraylist to store the indices is because we cannot keep the indices in ascending order.

The correct solution:

So the correct solution is to use a HashSet or LinkedHashSet.

Code (Java):

class RandomizedCollection {
    private List<Integer> list;
    private Map<Integer, LinkedHashSet<Integer>> map;
     
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }
     
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean ans = true;
         
        LinkedHashSet<Integer> indices;
        int loc = list.size();
         
        list.add(val);
         
        if (map.containsKey(val)) {
            ans = false;
            indices = map.get(val);
        } else {
            indices = new LinkedHashSet<>();
        }
        indices.add(loc);
        map.put(val, indices);
         
        return ans;
    }
     
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val) || map.get(val).isEmpty()) {
            return false;
        }
         
        // Get loc of the val to be removed
        //
        int locToRemove = map.get(val).iterator().next();
         
        // Remove the val
        //
        map.get(val).remove(locToRemove);
         
        if (locToRemove < list.size() - 1) {
         
            // Get the number to be swapped
            //
            int numToSwap = list.get(list.size() - 1);
 
            // Put the tail number to the location to be removed
            //
            list.set(locToRemove, numToSwap);
 
            // Update the loc
            //
            if (map.get(numToSwap).contains(list.size() - 1)) {
                map.get(numToSwap).remove(list.size() - 1);
            }
            map.get(numToSwap).add(locToRemove);
        }
         
        // Remove the val
        //
        list.remove(list.size() - 1);
         
        return true;
    }
     
    /** Get a random element from the collection. */
    public int getRandom() {
        if (list.isEmpty()) {
            return 0;
        }
         
        Random rand = new Random();
        int loc = rand.nextInt(list.size());
        return list.get(loc);
    }
}
 
/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Friday, July 27, 2018

Leetcode 380. Insert Delete GetRandom O(1)

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

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
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();

Analysis:

We can use a hashMap + array here.

Insert - insert the val to the tail of the array, and update the hash map.

Remove - swap the val to be deleted with the tail of the list node. Update the index in the hash map, and remove tail of the array

GetRandom - Get a random index in the array and return its value.

Code (Java):

class RandomizedSet {
    private List<Integer> list;
    private Map<Integer, Integer> map;
     
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = 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) {
        if (map.containsKey(val)) {
            return false;
        }
         
        int index = list.size();
        list.add(val);
        map.put(val, index);
         
        return true;
    }
     
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
         
        int indexRemove = map.get(val);
        int tail = list.get(list.size() - 1);
         
        swap(indexRemove, list.size() - 1);
        map.put(tail, indexRemove);
        list.remove(list.size() - 1);
        map.remove(val);
         
        return true;
    }
     
    /** Get a random element from the set. */
    public int getRandom() {
         
        if (list.isEmpty()) {
            return 0;
        }
         
        Random rand = new Random();
        int index = rand.nextInt(list.size());
         
        return list.get(index);
    }
     
    private void swap(int i, int j) {
        int temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}
 
/**
 * 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();
 */

Leetcode 370. Range Addition

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Given:

    length = 5,
    updates = [
        [1,  3,  2],
        [2,  4,  3],
        [0,  2, -2]
    ]

Output:

    [-2, 0, 3, 5, 3]

Explanation:

Initial state:
[ 0, 0, 0, 0, 0 ]

After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]

After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]

After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

Credits:
Special thanks to @vinod23 for adding this problem and creating all test cases.

Code (Java):

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] ans = new int[length];
         
        for (int[] update : updates) {
            int start = update[0];
            int end = update[1];
            int inc = update[2];
             
            ans[start] += inc;
            if (end + 1 < length) {
                ans[end + 1] += -inc;
            }
        }
 
        for (int i = 1; i < length; i++) {
            ans[i] += ans[i -1];
        }
         
        return ans;
    }
}

Analysis:
Time complexity: O(n + k), where n is the length, and k is the number of update operations.

Sunday, July 22, 2018

Leetcode 872. Leaf-Similar Trees

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2 == null;
        }
         
        if (root2 == null) {
            return root1 == null;
        }
         
        List<Integer> sequence1 = findLeafValueSequence(root1);
        List<Integer> sequence2 = findLeafValueSequence(root2);
         
        if (sequence1.size() != sequence2.size()) {
            return false;
        }
         
        for (int i = 0; i < sequence1.size(); i++) {
            int num1 = sequence1.get(i);
            int num2 = sequence2.get(i);
             
            if (num1 != num2) {
                return false;
            }
        }
         
        return true;
    }
     
    private List<Integer> findLeafValueSequence(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
         
        findLeafValueSequenceHelper(root, ans);
         
        return ans;
    }
     
    private void findLeafValueSequenceHelper(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }
         
        if (root.left == null && root.right == null) {
            ans.add(root.val);
            return;
        }
         
        findLeafValueSequenceHelper(root.left, ans);
        findLeafValueSequenceHelper(root.right, ans);
    }
}

Leetcode 874. Walking Robot Simulation

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31

Code (Java)

class Solution {
    private int curX = 0;
    private int curY = 0;
    private int curDir = 0;
    private int[][] directions = {{0,1}, {1,0}, {0, -1}, {-1, 0}};
     
    public int robotSim(int[] commands, int[][] obstacles) {
        int ans = 0;
         
        // step 1: put the obstacles into a hashset
        //
        Set<Long> set = new HashSet<>();
        for (int[] obstacle : obstacles) {
            long x =  (long) obstacle[0] + 30000;
            long y = (long) obstacle[1] + 30000;
            long hashCode = (x << 16) + y;
            set.add(hashCode);
        }
         
        // step 2: go to each command
        //
        for (int command : commands) {
            if (command == -1) {
                changeDirection(-1);
            } else if (command == -2) {
                changeDirection(-2);
            } else if (command >= 1 && command <= 9) {
                go(command, set);
                ans = Math.max(ans, curX * curX + curY * curY);
            }
        }
         
        return ans;
    }
     
    private void changeDirection(int direction) {
        if (direction == -1) {
            curDir = (curDir + 1 + 4) % 4;
        } else if (direction == -2) {
            curDir = (curDir - 1 + 4) % 4;
        }
    }
     
    private void go(int steps, Set<Long> set) {
        int[] direction = directions[curDir];
        int targetX = curX + steps * direction[0];
        int targetY = curY + steps * direction[1];
         
        for (int i  = 0; i < steps; i++) {
            curX += direction[0];
            curY += direction[1];
             
            long x = (long)curX + 30000;
            long y = (long)curY + 30000;
            long hashCode = (x << 16) + y;
            if (set.contains(hashCode)) {
                curX -= direction[0];
                curY -= direction[1];
                 
                break;
            }
        }
    }
}

Leetcode 875. Koko Eating Bananas

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

Approach 1: Binary Search

Intuition

Call an eating speed K a candidate if Koko can finish eating all the bananas within H hours while having an eating speed of K. This is motivated by the fact that we want to find the smallest candidate.

If K is a candidate, then any speed larger than K is also a candidate, as a faster speed would make her finish eating all bananas in at most the same amount of time.

Let X be the answer desired - the smallest candidate. Then every value less than X is not a candidate (because X is chosen as the smallest), and every value larger than X is a candidate (because of the reasoning above).

Algorithm

Say possible(K) is true if and only if K is a candidate. If we were to write out possible(0), possible(1), ..., it would look like [False, False, ..., False, True, True, ...]: with only the first X values being False, and the rest True.

We can binary search on these values to find the first X such that possible(X) is True: that will be our answer. Our loop invariant will be that possible(hi) is always True, and lo is always less than or equal to the answer. For more information on binary search, please visit [LeetCode Explore - Binary Search].

To find the value of possible(K), (ie. whether Koko with an eating speed of K can eat all bananas in H hours), we simulate it. For each pile of size p > 0, we can deduce that Koko finishes it in ((p-1) // K) + 1 hours, and we add these times across all piles and compare it to H.

Code (Java):

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int lo = 1;
        int hi = 1000000000;
         
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
             
            if (canFinish(mid, piles, H)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
         
        if (canFinish(lo, piles, H)) {
            return lo;
        } else {
            return hi;
        }
    }
     
    private boolean canFinish(int K, int[] piles, int H) {
        int time = 0;
        for (int cBananas : piles) {
            time += (cBananas - 1) / K + 1;
        }
         
        return time <= H;
    }
}

Another better solution with better low and high boundaries

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        Arrays.sort(piles);
        long total = 0;
        for(int pile : piles) total += pile;
        int min = (int)Math.ceil(total/(double)H);
        int max = piles[piles.length - 1];
        while (min < max){
            if (canFinish(piles, min, H)) return min;
            if (canFinish(piles, (min + max) / 2, H)) max = (min + max)/2;
            else min = (min + max) / 2 + 1;
        }
        return (int)min;
    }
    
    
    private boolean canFinish(int[] piles, int speed, int target){
        long counter = 0;
        for (int pile : piles){
            counter += Math.ceil(pile / (double)speed);
        }
        return (int)counter <= target;
    }
}