LeetCode - String Compression - Day15 (1/15/2020)
String Compression
Question
Given an array of characters, compress it in-place.
The length after compression must always be smaller than or equal to the original array.
Every element of the array should be a character (not int) of length 1.
After you are done modifying the input array in-place, return the new length of the array.
Follow up: Could you solve it using only O(1) extra space?
Example 1:
Input: ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: "aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
Example 2:
Input: ["a"] Output: Return 1, and the first 1 characters of the input array should be: ["a"] Explanation: Nothing is replaced.
Example 3:
Input: ["a","b","b","b","b","b","b","b","b","b","b","b","b"] Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"]. Explanation: Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12". Notice each digit has it's own entry in the array.
Note:
- All characters have an ASCII value in [35, 126].
- 1 <= len(chars) <= 1000.
What I though & Solution
For this question, what I came up with is to use the two pointers. Let's say there are two pointers called, "search" and "update". The "search" pointer will searches how many same characters show up on the array and "update" pointer indicates the point we updated the array.
Since the character that shows up once will not be changed and "update" pointer will not overcome "search" pointer, we can manage this by O(1) extra space.
public int compress(char[] chars) { int search = 0, update = 0; while (search < chars.length) { char curr = chars[search]; int count = 0; while (curr < chars.length && chars[search] == curr) { search++; count++; } chars[update++] = curr; if (count != 1) { for (char c : Integer.toString(count).toCharArray()) { chars[update++] = c; } } } return update; }
Time complexity
O(N)
Space complexity
O(1)
LeetCode - Longest Palindromic Substring- Day15 (1/15/2020)
Longest Palindromic Substring
Question
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd" Output: "bb"
What I though & Solution
It seem like DP question.
Let's translate the question to the math:
P(i, j) = 1. true if the substring Si...Sj is a palindrome. 2. false otherwise.
Therefore, P(i, j) = P(i - 1, j + 1) && Si == Sj
The base case are
P(i, i) = true P(i, i + 1) = (Si == Si+1)
private int low, maxLen; public String longestPalindrome(String s) { if (s.length() < 2) { return s; } for (int i = 0; i < s.length() - 1; i++) { expandPalindrome(s, i, i); expandPalindrome(s, i, i + 1); } return s.substring(low, low + maxLen); } private void expandPalindrome(String s, int j, int k) { while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) { j--; k++; } if (maxLen < k - j - 1) { low = j + 1; maxLen = k - j - 1; } }
Time complexity
O(n2)
Space complexity
O(n2)
LeetCode - Design Tic-Tac-Toe - Day15 (1/15/2020)
Design Tic-Tac-Toe
Question
Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves is allowed.
- A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board. TicTacToe toe = new TicTacToe(3); toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | toe.move(2, 2, 1); -> Returns 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| toe.move(1, 1, 2); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| toe.move(2, 0, 1); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| toe.move(1, 0, 2); -> Returns 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| toe.move(2, 1, 1); -> Returns 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|
Follow up:
Could you do better than O(n2) per move() operation?
What I though
Because I have solved the similar question of this, I set board[][] and try to manage it by adding 'X' and 'O' in move function.
However, once we try to check who wins, it takes O(n2) run time to find the answer.
Solution
The easiest way to manage the current situation of Tic-Tac-Toe is to use Integer.
Let's say if player 1 move his X, we increment the integer for the arrays matching with the coordinate.
Instead, if player 2 move his O, we decrement.
In this condition, if one of the element in the array reach n, it means either player 1 or 2 win.
In addition, we need to manage diagonal/anti-diagonal cases by using the same way.
class TicTacToe { private int[] rows; private int[] cols; private diagonal; private antiDiagonal; /** Initialize your data structure here. */ public TicTacToe(int n) { rows = new int[n]; cols = new int[n]; } /** Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. */ public int move(int row, int col, int player) { int toAdd = player == 1 ? 1 : -1; rows[row] += toAdd; cols[col] += toAdd; if (row == col) { diagonal += toAdd; } if (col == (cols.length - row - 1)) { antiDiagonal += toAdd; } int size = rows.length; if (Math.abs(rows[row]) == size || Math.abs(cols[col]) == size || Math.abs(diagonal) == size || Math.abs(antiDiagonal) == size) { return player; } return 0; } } /** * Your TicTacToe object will be instantiated and called as such: * TicTacToe obj = new TicTacToe(n); * int param_1 = obj.move(row,col,player); */
LeetCode - LRU Cache - Day14 (1/14/2020)
LRU Cache
Question
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Follow up: Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
What I though & Solution
According to the question, we need to have a hash-map to keep track of the keys and its values. However, at the same time, we need to cache these data. In that case, managing a hash-map by using a double linked list is one of the good strategies since we can easily change the order to represent caching system and have many data such as keys and values.
The photo above shows how we should hold data to implement LRU cache. By using this structure, we can realize O(1) time for put and get operations. It also allows to remove the first added node in O(1) time as well.
One advantage of double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.
One particularity about the double linked list implemented here is that there are pseudo head and pseudo tail to mark the boundary, so that we don't need to check the null node during the update.
class LRUCache { class ListNode { int key; int value; ListNode prev; ListNode next; } private void addNode(ListNode node) { node.prev = first; node.next = first.next; first.next.prev = node; first.next = node; } private void removeNode(ListNode node) { ListNode prev = node.prev; ListNode next = node.next; prev.next = next; next.prev = prev; } private void moveToHead(ListNode node) { removeNode(node); addNode(node); } private ListNode popLast() { ListNode res = last.prev; removeNode(res); return res; } private Map<Integer, ListNode> cache = new HashMap<>(); private int size; private int capacity; private ListNode first, last; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; first = new ListNode(); last = new ListNode(); first.next = last; last.prev = first; } public int get(int key) { ListNode node = cache.get(key); if (node == null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { ListNode node = cache.get(key); if (node == null) { ListNode newNode = new ListNode(); newNode.key = key; newNode.value = value; cache.put(key, newNode); addNode(newNode); size++; if (size > capacity) { ListNode last = popLast(); cache.remove(last.key); size--; } } else { node.value = value; moveToHead(node); } } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
Time complexity
O(1) for both put and get.
Space complexity
O(capacity) since the space is used only for a hashmap and double linked list which at most capacity + 1 elements.
LeetCode - Reverse Words in a String - Day12 (1/12/2020)
Reverse Words in a String
Question
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue" Output: "blue is sky the"
Example 2:
Input: " hello world! " Output: "world! hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Note:
- A word is defined as a sequence of non-space characters.
- Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
- You need to reduce multiple spaces between two words to a single space in the reversed string.
What I though & Solution
Let's split string by white space, tab, and any blank then, construct a new string in the reverse order.
According to the stack overflow, the \\s is equivalent to [ \\t\\n\\x0B\\f\\r], so I use this to split a string.
public String reverseWords(String s) { String[] arr = s.split("\\s+"); String res = ""; for (int i = arr.length - 1; i >= 0; i--) { res += arr[i] + " "; } return res.trim(); }
Time complexity
O(N), where N is a number of characters in the input string.
Space complexity
O(N), to store the result of a split by spaces.
LeetCode - Trapping Rain Water - Day12 (1/12/2020)
Trapping Rain Water
Question
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
What I though & Solution
According to the question, what we need to do is that for each element in the array, we find the max level of water it can trap the rain, which is equal to the min of max height of bars on both the sides minus its own height.
Of course, we can traverse from both side which will have O(n2) runtime, but we can optimize to only one traversal.
Let's think about the requirement again.
If the left max bar is lower than the right max bar, then the amount of trapped water depends on the left max bar and vice versa.
So, we can use two pointer and keep track of the left max bar, the right max bar and current positions.
public int trap(int[] height) { int left = 0; int right = height.length - 1; int ans = 0; int leftMax = 0; int rightMax = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { ans += (leftMax - height[left]); } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { ans += (rightMax - height[right]); } right--; } } return ans; }
Time complexity
O(N) since it requires single iteration.
Space complexity
O(1) extra space to store left, right, leftMax, and rightMax.
LeetCode - Valid Tic-Tac-Toe State - Day 12 (1/12/2020)
Valid Tic-Tac-Toe State
Question
A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.
Here are the rules of Tic-Tac-Toe:
- Players take turns placing characters into empty squares (" ").
- The first player always places "X" characters, while the second player always places "O" characters.
- "X" and "O" characters are always placed into empty squares, never filled ones.
- The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
- The game also ends if all squares are non-empty.
- No more moves can be played if the game is over.
What I thought
So, the key point of this question is to break down the requirement to some small condition. For this question, there are a few conditions:
Either "XXX" or "OOO" will show up only once.
X shows up n times and O shows up m times (n >= 0 and m >= 0 and m + 1 >= n >= m)
Once we translate them to the code, it will be:
public boolean validTicTacToe(String[] board) { int flagRow = 0; Map<Character, Integer> map = new HashMap<>(); map.put('X', 0); map.put('O', 0); for (String s : board) { if (s.equals("XXX") || s.equals("OOO")) { flagRow++; } for (char c : s.toCharArray()) { if (map.containsKey(c)) { map.put(c, map.get(c) + 1); } } } if (flagRow > 1) { return false; } if (map.get('X') < map.get('O') || map.get('X') > map.get('O') + 1) { return false; } return true; }
Yes, of course, it is not valid code because we ignore the case when "XXX" and "OOO" in the column. In addition, it doesn't cover the case when "O" shows up after "XXX" has already shown up.
Thus, we need to think of different approaches.
Solution: Ad-Hoc
Okay, let's rethink the conditions for a tic-tac-toe board to be valid.
Since players take turns, the number of 'X's must be equal to or one greater than the number of 'O's.
A player will win in the condition when:
- If the first player wins, the number of 'X's is one more than the number of 'O's
- If the second player wins, the number of 'X's is equal to the number of 'O's.
The board can't simultaneously have three 'X's and three 'O's in a row: once one player has won (on their move), there are no subsequent moves.
The key point is to keep track of the win case by using a private method.
public boolean validTicTacToe(String[] board) { int xCount = 0, oCount = 0; for (String row: board) { for (char c : row.toCharArray()) { if (c == 'X') xCount++; if (c == 'O') oCount++; } } if (oCount != xCount && oCount != xCount - 1) return false; if (win(board, 'X') && oCount != xCount - 1) return false; if (win(board, 'O') && oCount != xCount) return false; return true; } public boolean win(String[] B, char P) { // B: board, P: player for (int i = 0; i < 3; i++) { if (P == B[0].charAt(i) && P == B[1].charAt(i) && P == B[2].charAt(i)) return true; if (P == B[i].charAt(0) && P == B[i].charAt(1) && P == B[i].charAt(2)) return true; } if (P == B[0].charAt(0) && P == B[1].charAt(1) && P == B[2].charAt(2)) return true; if (P == B[0].charAt(2) && P == B[1].charAt(1) && P == B[2].charAt(0)) return true; return false; }
Time and Space Complexity
O(1) since the size of array is always 3, the length of the each string will be 3 and we don't have to use additional array.
