Leetcode 394. Decode String

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution:
Use two stacks. One store the number, another store the previous partial result. 

Code (Java):

class Solution {
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        
        String ans = "";
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    int digit = Character.getNumericValue(s.charAt(i));
                    num = num * 10 + digit;
                    i++;
                }
                
                numStack.push(num);
            } else if (c == '[') {
                strStack.push(ans);
                i++;
                ans = "";
            } else if (c == ']') {
                int num = numStack.pop();
                StringBuilder sb = new StringBuilder(strStack.pop());
                for (int r = 0 ; r < num; r++) {
                    sb.append(ans);
                }
                
                ans = sb.toString();
                i++;
            } else {
                ans += c;
                i++;
            }
        }
        
        return ans;
    }
}

Leetcode 366. Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2          

2. Now removing the leaf [2] would result in this tree:

          1          

3. Now removing the leaf [1] would result in the empty tree:

          []         

Solution:
DFS + backtracking. Get depth of each node, and group the nodes with the same depth together.

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 List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if (root == null) {
            return ans;
        }
        
        findLeavesHelper(root, ans);
        
        return ans;
    }
    
    private int findLeavesHelper(TreeNode root, List<List<Integer>> ans) {
        if (root == null) {
            return -1;
        }
        
        int left = findLeavesHelper(root.left, ans);
        int right = findLeavesHelper(root.right, ans);
        
        int depth = Math.max(left, right) + 1;
        
        if (depth == ans.size()) {
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            ans.add(list);
        } else {
            List<Integer> list = ans.get(depth);
            list.add(root.val);
        }
        
        
        return depth;
    }
}

Leetcode 364. Nested List Weight Sum II

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.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8 
Explanation: Four 1's at depth 1, one 2 at depth 2.

Example 2:

Input: [1,[4,[6]]]
Output: 17 
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

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 {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @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();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @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();
 * }
 */
class Solution {
    private int maxDepth = 0;
    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) {
            return 0;
        }
        
        getDepth(1, nestedList);
        
        return depthSumHelper(maxDepth, nestedList);
    }
    
    private void getDepth(int level, List<NestedInteger> nestedList) {
        maxDepth = Math.max(maxDepth, level);
        for (NestedInteger n : nestedList) {
            if (!n.isInteger()) {
                getDepth(level + 1, n.getList());
            }
        }
    }
    
    private int depthSumHelper(int depth, List<NestedInteger> nestedList) {
        int sum = 0;
        for (NestedInteger n : nestedList) {
            if (n.isInteger()) {
                sum += depth * n.getInteger();
            } else {
                sum += depthSumHelper(depth - 1, n.getList());
            }
        }
        
        return sum;
    }
}

Leetcode: Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

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

Understand the problem:

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. 1 <= N <= 10^9
2. 2 <= A <= 40000
3. 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.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. 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();
 */

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();

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.

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:

1. 0 <= commands.length <= 10000
2. 0 <= obstacles.length <= 10000
3. -30000 <= obstacle[i][0] <= 30000
4. -30000 <= obstacle[i][1] <= 30000
5. 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;
    }
}

Leetcode 463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

Code (Java):

class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int perimeter = 0;
        
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == false && grid[i][j] == 1) {
                    perimeter = islandPerimeterHelper(i, j, grid, visited);
                    break;
                }
            }
        }
        
        return perimeter;
    }
    
    private int islandPerimeterHelper(int row, int col, int[][] grid, boolean[][] visited) {
        int m = grid.length;
        int n = grid[0].length;
        
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return 1;
        }
        
        if (grid[row][col] == 0) {
            return 1;
        }
        
        if (visited[row][col] == true) {
            return 0;
        }
        
        visited[row][col] = true;
        
        return islandPerimeterHelper(row - 1, col, grid, visited) + 
            islandPerimeterHelper(row + 1, col, grid, visited) + 
            islandPerimeterHelper(row, col - 1, grid, visited) + 
            islandPerimeterHelper(row, col + 1, grid, visited);
    }
}

Leetcode 657. Judge Route Circle

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L(Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

Input: "UD"
Output: true

Example 2:

Input: "LL"
Output: false

Code (Java):

class Solution {
    public boolean judgeCircle(String moves) {
        if (moves == null || moves.length() == 0) {
            return true;
        }
        
        int x = 0;
        int y = 0;
        
        for (int i = 0; i < moves.length(); i++) {
            char move = moves.charAt(i);
            switch (move) {
                case 'U':
                    y++;
                    break;
                case 'D':
                    y--;
                    break;
                case 'L':
                    x--;
                    break;
                case 'R':
                    x++;
                    break;
            }
        }
        
        return x == 0 && y == 0;
    }
}