Add and Search Word - Data structure design | Leetcode

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first. 

 

---

Solution: The difference between this algorithm and the basic trie algorithm is just in the way we handle the dots. When we see a dot, we take all the children of the current node, and check whether the remaining characters in the word can be found. If so, it is a match. If we have a dot and we get a TERMINAL node, then the word is not found since the trie search terminates halfway in the word.

public class WordDictionary {

    private static class TrieNode {
        private Map<Character, TrieNode> children = new HashMap<>();
    }
    
    private TrieNode root = new TrieNode();
    private static final char TERMINAL = (char) -1;
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode child = node.children.get(c);
            if (child == null) {
                child = new TrieNode();
                node.children.put(c, child);
            }
            node = child;
        }
        node.children.put(TERMINAL, node);
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return searchFrom(word, 0, root);
    }
    
    private boolean searchFrom(String word, int start, TrieNode node) {
        for (int i = start; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                return searchDot(word, i + 1, node);
            }
            node = node.children.get(c);
            if (node == null) {
                return false;
            }
        }
        return node.children.containsKey(TERMINAL);
    }
    
    private boolean searchDot(String word, int i, TrieNode node) {
        for (TrieNode child: node.children.values()) {
            // If we hit a terminal node, that means the word is not found.
            if (child == node) continue;
            
            if (searchFrom(word, i, child)) {
                return true;
            }
        }
        return false;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

Course Schedule II | Leetcode

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

---

Solution: I prefer using DFS to detect a cycle because the algorithm seems simpler than using topological sort. The trick is the order to add the nodes. For the answer array, start adding from the last position to the first after we have determined that there is no cycle.

public class Solution {
    private int[] answer;
    private int index = 0;
    
    private class Node {
        private int val;
        private List<Node> inEdges = new ArrayList<>();
        private boolean seen;
        private boolean inRecursiveStack;
        
        private Node(int val) { this.val = val; }
        
        private boolean hasCycle() {
            if (seen) return false;
            if (inRecursiveStack) return true;
            inRecursiveStack = true;
            
            for (Node node: inEdges) {
                if (node.hasCycle()) return true;
            }
            
            answer[--index] = val;
            inRecursiveStack = false;
            seen = true;
            return false;
        }
    }
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Node[] graph = new Node[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new Node(i);
        }
        
        for (int[] prereq: prerequisites) {
            Node in = graph[prereq[0]];
            Node out = graph[prereq[1]];
            out.inEdges.add(in);
        }
        
        answer = new int[numCourses];
        index = numCourses;
        
        for (int i = 0; i < numCourses; i++) {
            if (graph[i].hasCycle()) {
                return new int[0];
            }
        }
        
        return answer;
    }
}

Minimum Size Subarray Sum | Leetcode

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

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

---

Solution: Iterate through the array, maintaining a start position, the current minimum length, and the current sum from the start position to the current position. As we go through the array, shorten the subarray as much as possible by advancing the start position. If we get the current sum greater or equal to s, update the minimum length accordingly.

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;
        
        int start = 0;
        int sum = 0;
        Integer min = null;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            
            while ((start < i) && ((sum - nums[start]) >= s)) {
                sum -= nums[start];
                start++;
            }
            
            if (sum < s) continue;
            
            int curLength = i - start + 1;
            if ((min == null) || (min > curLength)) {
                min = curLength;
            }
        }
        
        return (min == null) ? 0 : min;
    }
}

Implement Trie (Prefix Tree) | Leetcode

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

---

Solution: The main thing here is really the data structure to store the trie. I found that using a map of character to TrieNode is sufficient to represent the structure. The other parts of the code only consist of single for loops.

class TrieNode {
    // Initialize your data structure here.
    Map<Character, TrieNode> children = new HashMap<>();
}

public class Trie {
    private static final char TERMINAL = (char) -1;
    private TrieNode root = new TrieNode();

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode child = node.children.get(c);
            if (child == null) {
                child = new TrieNode();
                node.children.put(c, child);
            }
            node = child;
        }
        node.children.put(TERMINAL, node);
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            node = node.children.get(c);
            if (node == null) return null;
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        if (node == null) return false;
        return node.children.containsKey(TERMINAL);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return (node != null);
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

Course Schedule | Leetcode

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

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

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

---

Solution: The hints tells us that there are 3 possible algorithms to solve this problem. I personally find the finding cycles in a directed graph algorithm the simplest to understand, so that is what I have here.

public class Solution {
    private static class Course {
        private boolean seen;
        private boolean inRecursionStack;
        private List<Course> prerequisites = new ArrayList<>();
    
        private boolean hasCycle() {
            if (seen) return false;
            if (inRecursionStack) return true;
            
            inRecursionStack = true;
            
            for (Course prereq: prerequisites) {
                if (prereq.hasCycle()) return true;
            }
            
            inRecursionStack = false;
            seen = true;
            return false;
        }
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Create all course objects.
        Course[] courses = new Course[numCourses];
        for (int i = 0; i < numCourses; i++) {
            courses[i] = new Course();
        }
        
        // Add all course prerequisites.
        for (int[] prereq: prerequisites) {
            Course course1 = courses[prereq[0]];
            Course course2 = courses[prereq[1]];
            course1.prerequisites.add(course2);
        }
        
        // Check for cycles.
        for (Course course: courses) {
            if (course.hasCycle()) return false;
        }
        
        return true;
    }
}

Reverse Linked List | Leetcode

Reverse a singly linked list.

click to show more hints.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

---

Solution: Iterate through the list, getting the next node to point to the previous node.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }
}

Isomorphic Strings | Leetcode

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

---

Solution: Maintain a two-way mapping (c1 <-> c2) between each character in the string in the same index. If we find that something was previous mapped but not matching the current characters in s and t, then the strings are not isomorphic. If we did not find any discrepancies, return true.

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            int c1 = s.charAt(i);
            int c2 = t.charAt(i);
            
            Integer m1 = map1.get(c1);
            if (m1 != null && m1 != c2) return false;
            
            Integer m2 = map2.get(c2);
            if (m2 != null && m2 != c1) return false;
            
            map1.put(c1, c2);
            map2.put(c2, c1);
        }
        
        return true;
    }
}

Count Primes | Leetcode

Description:
Count the number of prime numbers less than a non-negative number, n.

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

---

Solution: Use the Sieve of Eratosthenes algorithm to find prime numbers.

public class Solution {
    public int countPrimes(int n) {
        // Use <= 2 because we are taking only numbers
        // less than n, excluding n.
        if (n <= 2) return 0;
        
        // We use "notPrime" instead of "prime" so that we
        // don't need to initialize them to all true to begin.
        boolean[] notPrime = new boolean[n];
        int sqrt = (int) Math.sqrt(n - 1);
        
        for (int i = 2; i <= sqrt; i++) {
            if (notPrime[i]) continue;
            
            for (int j = i + i; j < n; j += i) {
                notPrime[j] = true;
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) count++;
        }
        return count;
    }
}

Remove Linked List Elements | Leetcode

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

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

---

Solution: First remove all the starting nodes with node.val == val. Update the head pointer accordingly to return later. Iterate through the remaining list while maintaining the previous and current pointers. Whenever we find a matching "curr.val == val", remove it by doing "prev.next = curr.next". Return the head pointer as the answer.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while (true) {
            if (head == null) return null;
            if (head.val != val) break;
            head = head.next;
        }

        ListNode prev = head;
        ListNode curr = prev.next;
        
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        
        return head;
    }
}

Happy Number | Leetcode

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 1² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

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

---

Solution: Maintain a hash set to remember all the numbers that we have already seen. Loop infinitely. If we get 1, then n is a happy number. If we get a number that we have already seen, that means we are going to loop infinitely, so n is not a happy number.

public class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        seen.add(n);
        
        while (true) {
            if (n == 1) return true;
            
            String s = Integer.toString(n);
            n = 0;
            for (int i = 0; i < s.length(); i++) {
                int c = s.charAt(i) - '0';
                n += c * c;
            }
            
            if (seen.contains(n)) return false;
            seen.add(n);
        }
    }
}

Bitwise AND of Numbers Range | Leetcode

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

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

---

Solution: A trick question. See http://yucoding.blogspot.com/2015/06/leetcode-question-bitwise-and-of.html for a good explanation.

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int pos = 0;
        while (m < n) {
            pos++;
            m >>= 1;
            n >>= 1;
        }
        return m << pos;
    }
}

Number of Islands | Leetcode

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

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

---

Solution: Maintain a boolean grid to mark whether each element in the grid has been seen or not. Iterate through each element in the grid. For each grid element that is not yet seen and is a '1', add the island count and mark all reachable '1' elements as seen.

public class Solution {
    private char[][] grid;
    private int len1;
    private int len2;
    private boolean[][] seen;

    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        
        this.grid = grid;
        len1 = grid.length;
        len2 = grid[0].length;
        seen = new boolean[len1][len2];
        
        int count = 0;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (seen[i][j]) continue;
                if (grid[i][j] == '0') continue;
                count++;
                markIsland(i, j);
            }
        }
        return count;
    }

    private void markIsland(int i, int j) {
        if (seen[i][j]) return;
        seen[i][j] = true;
        if (i >= 1       && grid[i - 1][j] == '1') markIsland(i - 1, j);
        if (i < len1 - 1 && grid[i + 1][j] == '1') markIsland(i + 1, j);
        if (j >= 1       && grid[i][j - 1] == '1') markIsland(i, j - 1);
        if (j < len2 - 1 && grid[i][j + 1] == '1') markIsland(i, j + 1);
    }
}

Binary Tree Right Side View | Leetcode

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

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

---

Solution: Maintain a list of integers "answer" such that the value at index i is the last node we we saw at height i. Traverse the tree in breadth-first search (BFS) order, keeping the height info of each node. For each node, set the value in "answer" at index "height" with the node's value. When you are done traversing, you will get the answer in "answer".

I can think of two other ways to solve the problem:

1. Maintain two queues, one for the current level and another for the next level. Traverse BFS by using the current level queue and add all children nodes to the next level queue. At the end of each level, add the last seen node's value to the answer.
2. Traverse BFS as per the algoritm shown below. Whenever the height changes, add the last seen node's value to the answer. After the traversal, if we have any level not added to the answer yet, add it.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static class TreeNodeWithHeight {
        private TreeNode treeNode;
        private int height;
        
        private TreeNodeWithHeight(TreeNode treeNode, int height) {
            this.treeNode = treeNode;
            this.height = height;
        }
    }
    
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return Collections.emptyList();
        
        List<Integer> answer = new ArrayList<>();
        LinkedList<TreeNodeWithHeight> bfsQueue = new LinkedList<>();
        bfsQueue.addLast(new TreeNodeWithHeight(root, 0));
        
        do {
            TreeNodeWithHeight nodeWithHeight = bfsQueue.removeFirst();
            TreeNode node = nodeWithHeight.treeNode;
            int height = nodeWithHeight.height;
            
            if (height == answer.size()) {
                answer.add(node.val);
            } else {
                answer.set(height, node.val);
            }
            
            if (node.left != null) {
                bfsQueue.addLast(new TreeNodeWithHeight(node.left, height + 1));
            }
            if (node.right != null) {
                bfsQueue.addLast(new TreeNodeWithHeight(node.right, height + 1));
            }
        } while (!bfsQueue.isEmpty());
        
        return answer;
    }
}

House Robber | Leetcode

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

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

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

---

Solution: The dynamic programming formula is:

i = 0   ->  nums[0]
i = 1   ->  max(nums[0], nums[1])
i >= 2  ->  f[i] = max(f[i - 1], f[i - 2] + nums[i])

The final answer will be stored in f[nums.length - 1].

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

        return f[nums.length - 1];
    }
}

Number of 1 Bits | Leetcode

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

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

---

Solution: Extract each bit at position i using "bit = n & (1 << i)".

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                count++;
            }
        }
        return count;
    }
}

Reverse Bits | Leetcode

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?
Related problem: Reverse Integer

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

---

Solution: As in any reverse operation, start iterating from the start and the end. It does not matter if you start iterating from the middle or from the two ends. Swap the current first and last bits. The code for bit swap looks different from that of swapping two variables. We use "(n >> i) & 1" to extract a bit's value at position i. Then we use "n ^= (1 << i)" to toggle the bit's value at position i.

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int first = 0;
        int last = 31;
        do {
            int firstBit = (n >> first) & 1;
            int lastBit = (n >> last) & 1;
            if (firstBit != lastBit) {
                n ^= (1 << first) | (1 << last);
            }
            first++;
            last--;
        } while (first < last);
        return n;
    }
}

Rotate Array | Leetcode

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Hint:
Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

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

---

Solution: First Adjust k by doing k %= n so that we do not rotate redundantly.

Perform a three-reverse operation. It is either you know it or you don't.

http://articles.leetcode.com/2010/04/rotating-array-in-place.html

public class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    
    private void reverse(int[] nums, int first, int last) {
        while (first < last) {
            int temp = nums[first];
            nums[first] = nums[last];
            nums[last] = temp;
            first++;
            last--;
        }
    }
}

Best Time to Buy and Sell Stock IV | Leetcode

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

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

---

Solution: There are two parts needed to solve this problem. The first part is the simple case, when k >= length / 2, you can have as many transactions as you want. In this case, just buy and sell everyday when there is a profit to be made.

The second part is the dynamic programming part. Go through the prices array and simulate sell or hold on each price point. Then you will get the maximum profit in the last element of the sell array.

Algorithm 1 is the more easily understandable solution, but does not pass big test cases.
Algorithm 2 is the solution that will pass the leetcode submission.

Algorithm 1: Does not pass big test cases

public class Solution {
    private Integer[][] maxProfitCache;
    private int[] prices;
    
    public int maxProfit(int k, int[] prices) {
        maxProfitCache = new Integer[prices.length][prices.length];
        this.prices = prices;
        return maxProfit(k, 0, prices.length - 1);
    }
    
    private int maxProfit(int k, int first, int last) {
        if (first >= last) return 0;
        int max = maxProfit(first, last);
        if (k == 1) return max;
        
        for (int i = first + 1; i < last; i++) {
            max = Math.max(max, maxProfit(k - 1, first, i) + maxProfit(i, last));
        }
        return max;
    }
    
    private int maxProfit(int first, int last) {
        Integer cached = maxProfitCache[first][last];
        if (cached != null) return cached;

        int max = 0;
        int lowest = prices[first];
        for (int i = first + 1; i <= last; i++) {
            lowest = Math.min(lowest, prices[i]);
            max = Math.max(max, prices[i] - lowest);
        }
        
        maxProfitCache[first][last] = max;
        return max;
    }
}

Algorithm 2: Dynamic Programming

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int length = prices.length;
        if (length < 2) return 0;
        
        // Simple case.
        if (k >= length / 2) {
            int profit = 0;
            for (int i = 1; i < length; i++) {
                profit += Math.max(prices[i] - prices[i - 1], 0);
            }
            return profit;
        }
        
        // Dynamic programming.
        int[] hold = new int[k + 1];
        int[] sell = new int[k + 1];
        
        Arrays.fill(hold, Integer.MIN_VALUE);

        for (int price: prices) {
            for (int i = 1; i <= k; i++) {
                sell[i] = Math.max(sell[i], hold[i] + price);
                hold[i] = Math.max(hold[i], sell[i - 1] - price);
            }
        }
        
        return sell[k];
    }
}

Repeated DNA Sequences | Leetcode

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

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

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

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

---

Solution: Go through the string one character at a time. For each position i, take the current 10-character substring starting at position i. Maintain a map to remember whether we have seen the string (seen.get(t) == true), or we have already added it to our answer (seen.get(t) == false). If we have not seen the string yet, just add it to the map. The encode() method to convert a string into an integer is just to save memory to pass leetcode's submission.

The solution given here is somewhat optimal in memory use, but not optimal in speed. We could have chosen to update the last encode() value given the old lost character and the newly-gained character, for each next 10-character string. But that would make the code much more complicated and not easily readable. Therefore I have favored readability over performance in the code below, since it passes leetcode's submission anyway.

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Map<Integer, Boolean> seen = new HashMap<>();
        List<String> answer = new ArrayList<>();
        
        for (int i = 0, last = s.length() - 10; i <= last; i++) {
            String t = s.substring(i, i + 10);
            int code = encode(t);
            
            if (seen.containsKey(code)) {
                if (seen.get(code)) {
                    answer.add(t);
                    seen.put(code, false);
                }
            } else {
                seen.put(code, true);
            }
        }
        
        return answer;
    }
    
    private int encode(String s) {
        int code = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'A': code++;
                case 'C': code++;
                case 'G': code++;
                case 'T': code++;
            }
            code *= 4;
        }
        return code;
    }
}

Largest Number | Leetcode

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

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

---

Solution: Convert the numbers into a string array. This is because we need to operate them in strings for sorting, so we do not need to reconvert them to strings everytime we need it. Sort the string array using a special order. The comparison order is the key to this question. First, the numbers should be sorted in descending order (highest to lowest), so you have to use the opposite order of a JDK String.compareTo() method. Second, for any two number strings, you compare them by checking if putting one before the other is greater. For example, for "128" and "12", check if "12812" is greater than "12128". This will always work because since these two numbers have the same prefix, they will always be contiguous to other numbers with the same prefix in sorted order. Hence comparing them by putting them adjacent to each other will work.

public class Solution {
    public String largestNumber(int[] nums) {
        // Convert to array of strings.
        String[] s = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            s[i] = Integer.toString(nums[i]);
        }
        
        // Sort by desired order.
        Arrays.sort(s, (x, y) -> (y + x).compareTo(x + y));
        
        // Form one large string.
        StringBuilder sb = new StringBuilder();
        for (String t: s) {
            // Skip leading zeros.
            if (sb.length() == 0 && t.equals("0")) {
                continue;
            }
            sb.append(t);
        }
        
        // If empty, return 0.
        return (sb.length() != 0) ? sb.toString() : "0";
    }
}

Dungeon Game | Leetcode

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

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

---

Solution: See http://leetcodesolution.blogspot.com/2015/01/leetcode-dungeon-game.html.

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int len1 = dungeon.length;
        int len2 = dungeon[0].length;
        int[][] hp = new int[len1][len2];
        
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                if (i == len1 - 1 && j == len2 - 1) {
                    hp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                } else if (i + 1 == len1) {
                    hp[i][j] = Math.max(1, hp[i][j + 1] - dungeon[i][j]);
                } else if (j + 1 == len2) {
                    hp[i][j] = Math.max(1, hp[i + 1][j] - dungeon[i][j]);
                } else {
                    hp[i][j] = Math.max(1, Math.min(hp[i][j + 1], hp[i + 1][j]) - dungeon[i][j]);
                }
            }
        }
        
        return hp[0][0];
    }
}

Binary Search Tree Iterator | Leetcode

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

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

---

Solution: Maintain a stack of nodes which will get a size at most equal to the height of the tree. First push the root node into the stack. Pop the top node off the stack. If this node is a leaf node, then return it. If not, push the right node, then the node itself as a leaf node (a new node), and the left node into the stack. The trick to avoid returning the same node twice is to make the current node a leaf node by removing its children, then push the new childless node back into the stack.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {

    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        if (root != null) stack.push(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        while (true) {
            TreeNode node = stack.pop();
            
            if (node.left == null && node.right == null) {
                return node.val;
            }
            
            if (node.right != null) {
                stack.push(node.right);
            }
            
            stack.push(new TreeNode(node.val));
            
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

Factorial Trailing Zeroes | Leetcode

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

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

---

Solution: The idea is to count the number of factors of 5 in all of the numbers from 1 to n inclusive. 5, 10, 15, 20 count as one factor of 5 each. 25 counts as two factors of 5. We count the number of 5's because a zero is obtained by multiplying 2 by 5, and since there are surely more factors of 2 than factors of 5, we only need to count the number of 5'.

A good lengthy explanation beyond what I can write:

      http://www.programmerinterview.com/index.php/java-questions/find-trailing-zeros-in-factorial/

public class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n >= 5) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

Excel Sheet Column Title | Leetcode

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

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

---

Solution: Need to be very careful with the boundary conditions. Subtract n by 1 so that 0 -> A, 1 -> B, ..., 25 -> Z.

Example: Input n = 26. First digit is (n - 1) % 26 = 25 -> Z. Answer is AZ.

Example: Input n = 27. First digit is (n - 1) % 26 = 0 -> A. Set n = ((n - 1) / 26) = 1. Second digit is (n - 1) % 26 = 0 -> A. Answer is AA.

Example: Input n = 52. First digit is (n - 1) % 26 = 25 -> Z. Set n = ((n - 1) / 26) = 1. Second digit is (n - 1) % 26 = 0 -> A. Answer is AZ.

public class Solution {
    public String convertToTitle(int n) {
        StringBuilder sb = new StringBuilder();
        while (true) {
            n--;
            sb.append((char) ('A' + (n % 26)));
            if (n < 26) break;
            n /= 26;
        }
        return sb.reverse().toString();
    }
}

Fraction to Recurring Decimal | Leetcode

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

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

---

Solution: Watch out for negative numbers and boundary integer values in the input. First append the whole number part before the decimal point (straightforward). Loop to append the decimal numbers digit by digit. The way to do this is to use the formula: digit = (remainder * 10 / denominator). Keep track of the starting position of each remainder. If we get a remainder that we have seen before, enclose the recurring portion in parentheses and return. Else the remainder will go down to zero eventually so return when that happens.

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return "NaN";
        
        StringBuilder sb = new StringBuilder();
        
        // Fix negatives.
        long numer = numerator;
        long denom = denominator;
        if ((numerator < 0) ^ (denominator < 0)) {
            sb.append('-');
            if (numerator < 0) numer = -numer;
            if (denominator < 0) denom = -denom;
        }
        
        // Append number till decimal point.
        sb.append(numer / denom);
        long remainder = numer % denom;
        if (remainder == 0) return sb.toString();
        sb.append('.');
        
        // Append decimal numbers.
        Map<Long, Integer> indexOfRemainder = new HashMap<>();
        do {
            // Found recurring number, so insert parentheses and return.
            if (indexOfRemainder.containsKey(remainder)) {
                int index = indexOfRemainder.get(remainder);
                sb.insert(index, '(').append(')');
                break;
            }
            
            // Insert next digit.
            indexOfRemainder.put(remainder, sb.length());
            remainder *= 10;
            sb.append(remainder / denom);
            remainder %= denom;
        } while (remainder != 0);
        
        return sb.toString();
    }
}

Compare Version Numbers | Leetcode

Compare two version numbers version1 and version2.

If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

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

---

Solution: Split the version strings into arrays of numbers. Iterate through the arrays until the maximum of the two array lengths. In each iteration i, compare the current number at index i. If they are different, return the answer immediately (1 or -1). If we exit the loop without an answer, that means both versions are equal, so return 0.

public class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int maxLen = Math.max(v1.length, v2.length);

        for (int i = 0; i < maxLen; i++) {
            int n1 = (i < v1.length) ? Integer.parseInt(v1[i]) : 0;
            int n2 = (i < v2.length) ? Integer.parseInt(v2[i]) : 0;
            
            if (n1 > n2) return 1;
            if (n1 < n2) return -1;
        }
        
        return 0;
    }
}

Maximum Gap | Leetcode

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

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

---

Solution: Use bucket sort, but within each bucket, we only need to keep the min and max values. After sorting, iterate through the buckets. The maximum gap is the max of (bucket.max - bucket.min), or (bucket.min - prevBucket.max), where prevBucket is the last bucket which has any elements in it (i.e. not null).

public class Solution {
    private static class Bucket {
        private int min = Integer.MAX_VALUE;
        private int max = Integer.MIN_VALUE;
        
        private void add(int n) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
    }
    
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        
        // Find min and max.
        int min = IntStream.of(nums).min().getAsInt();
        int max = IntStream.of(nums).max().getAsInt();
        
        // Bucket sort.
        int gap = (max - min + nums.length) / nums.length;
        Bucket[] buckets = new Bucket[nums.length];
        
        for (int n: nums) {
            int b = (n - min) / gap;
            if (buckets[b] == null) buckets[b] = new Bucket();
            buckets[b].add(n);
        }
        
        // Find max gap.
        int maxGap = 0;
        int prevMax = 0;
        
        for (Bucket b: buckets) {
            if (b == null) continue;
            maxGap = Math.max(maxGap, b.max - b.min);
            if (prevMax > 0) maxGap = Math.max(maxGap, b.min - prevMax);
            prevMax = b.max;
        }
        
        return maxGap;
    }
}

Find Peak Element | Leetcode

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

 

Note: Your solution should be in logarithmic complexity.

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

---

Solution: Iterate through the array. If the current element is greater than the left and right elements, then it is a peak element. Return its index (not its value) as the answer.

We will definitely have an answer, so return the last index if none of the previous elements were peak elements.

public class Solution {
    public int findPeakElement(int[] nums) {
        int last = nums.length - 1;

        for (int i = 0; i < last; i++) {
            boolean greaterThanLeft = (i == 0) || (nums[i] > nums[i - 1]);
            boolean greaterThanRight = (i == last) || (nums[i] > nums[i + 1]);
            
            if (greaterThanLeft && greaterThanRight) {
                return i;
            }
        }

        // Last element must be a peak element if we did not find anything else.
        return last;
    }
}

Intersection of Two Linked Lists | Leetcode

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

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

---

Solution: Get the lengths of each list. Make them the same length by skipping the first few node of the longer list. For each of the remaining nodes, check each one to see if they are the same node. If not found, then return null.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // Find the lengths of the two lists.
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);
        
        // Make both lists the same length by skipping the
        // first few nodes of one of the lists if needed.
        for (int i = lengthB; i < lengthA; i++) {
            headA = headA.next;
        }
        for (int i = lengthA; i < lengthB; i++) {
            headB = headB.next;
        }
        
        // Check each node to see if they are the same node.
        while (headA != null) {
            if (headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
        }
        
        // No intersection found.
        return null;
    }
    
    private int getLength(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }
}

Min Stack | Leetcode

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

---

Solution: Maintain two stacks internally. One is to hold all the elements. The other, minStack, is to only hold the current minimum elements. The current minimum element is always the top element of the minStack.

class MinStack {
    private LinkedList stack = new LinkedList<>();
    private LinkedList minStack = new LinkedList<>();
    
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        int x = stack.pop();
        if (x == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Find Minimum in Rotated Sorted Array II | Leetcode

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

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

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

Find the minimum element.

The array may contain duplicates.

---

Solution: I just copied and pasted my answer from http://choksheak.blogspot.com/2015/08/find-minimum-in-rotated-sorted-array.html and it got accepted right away.

public class Solution {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    } 
    
    private int findMin(int[] nums, int lo, int hi) {
        if (lo >= hi) return nums[hi];

        // If sub-array is sorted, return the first number.
        boolean isSorted = (nums[lo] < nums[hi]);
        if (isSorted) return nums[lo];

        // If sub-array is not sorted, then need to search in both halves.
        int mid = lo + (hi - lo) / 2;
        return Math.min(findMin(nums, lo, mid), findMin(nums, mid + 1, hi));
    }
}

Find Minimum in Rotated Sorted Array | Leetcode

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

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

Find the minimum element.

You may assume no duplicate exists in the array.

---

Solution: Use a modified binary search. In each sub-array, if the first number is less than the last number, then this sub-array is sorted, so just return the first number. If this sub-array is not sorted, then break the sub-array into two halves and return the minimum of the minimum numbers from each half.

public class Solution {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    } 
    
    private int findMin(int[] nums, int lo, int hi) {
        if (lo >= hi) return nums[hi];

        // If sub-array is sorted, return the first number.
        boolean isSorted = (nums[lo] < nums[hi]);
        if (isSorted) return nums[lo];

        // If sub-array is not sorted, then need to search in both halves.
        int mid = lo + (hi - lo) / 2;
        return Math.min(findMin(nums, lo, mid), findMin(nums, mid + 1, hi));
    }
}

Maximum Product Subarray | Leetcode

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

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

---

Solution: Use 1D dynamic programming, where max[i] is the maximum product ending at i, and min[i] is the minimum product ending at i.

max[i] = max(a[i], (max[i - 1] * a[i]), (min[i - 1] * a[i]))
min[i] = min(a[i], (max[i - 1] * a[i]), (min[i - 1] * a[i]))

We need min[i] because if a[i] is negative, then min[i] * a[i] would produce the biggest product.

public class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int curMax = max;
        int curMin = max;

        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];

            // We are changing curMax and curMin below,
            // so make sure to use the old value.
            int maxN = curMax * n;
            int minN = curMin * n;

            curMax = Math.max(Math.max(n, maxN), minN);
            curMin = Math.min(Math.min(n, minN), maxN);

            // Using "max = Math.max(max, curMax);"
            // here will exceed the leetcode time limit.
            if (curMax > max) max = curMax;
        }
        
        return max;
    }
}

Reverse Words in a String | Leetcode

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

---

Solution: Reverse the entire string. Then reverse each word. This means that we should refactor reverseChars() into its own method since we will use it a few times.

Remove all extra spaces. We could have done this when we reverse each word, but the code will be much simpler if we do this step separately.

It is better to do this in-place (update the same character array instead of creating a new array or StringBuilder) as that would require less memory. With a quick search online, I found that most solutions are not in-place and hence arguably are not optimal solutions for this problem.

public class Solution {
    public String reverseWords(String s) {
        if (s.length() == 0) return s;
        
        char[] a = s.toCharArray();
        
        // Reverse the entire string.
        reverseChars(a, 0, a.length - 1);

        // Reverse each word in place.
        int wordStart = -1;
        
        for (int i = 0; i < a.length; i++) {
            if (wordStart >= 0) {
                if (a[i] == ' ') {
                    reverseChars(a, wordStart, i - 1);
                    wordStart = -1;
                }
            } else {
                if (a[i] != ' ') {
                    wordStart = i;
                }
            }
        }

        // Remember to reverse the last word as we will not
        // hit a space at the end of it.
        if (wordStart >= 0) {
            reverseChars(a, wordStart, a.length - 1);
        }
        
        // Trim string and between words.
        int stringIndex = 0;
        boolean hasSpace = false;
        
        for (int i = 0; i < a.length; i++) {
            if (a[i] != ' ') {
                if (hasSpace) {
                    a[stringIndex++] = ' ';
                    hasSpace = false;
                }
                a[stringIndex++] = a[i];
            } else {
                if (stringIndex > 0) {
                    hasSpace = true;
                }
            }
        }
        
        return new String(a, 0, stringIndex);
    }
    
    private static void reverseChars(char[] a, int startInclusive, int endInclusive) {
        for (int i = startInclusive, j = endInclusive; i < j; i++, j--) {
            char c = a[i];
            a[i] = a[j];
            a[j] = c;
        }
    }
}

Evaluate Reverse Polish Notation | Leetcode

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

---

Solution: Use a stack to hold the numbers and the computation results. Iterate through the tokens from first to last. If you see a number, add it to the stack. If you see an operator, perform it on the top two elements of the stack, and then push the result back into the stack. When done, return the one and only value in the stack as the answer.

public class Solution {
    public int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (String token: tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    stack.push(-stack.pop() + stack.pop());
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int denom = stack.pop();
                    stack.push(stack.pop() / denom);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}