SWE Interview preparation

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/ Given a string  s , determine if it is  valid . A string  s  is  valid  if, starting with an empty string  t = "" , you can  transform  t  into  s  after performing the following operation  any number of times : Insert string  "abc"  into any position in  t . More formally,  t  becomes  t left  + "abc" + t right , where  t == t left  + t right . Note that  t left  and  t right  may be  empty . Return  true   if  s  is a  valid  string, otherwise, return   false .   Example 1: Input: s = "aabcbc" Output: true Explanation: "" -> " abc " -> "a abc bc" Thus, "aabcbc" is valid. Example 2: Input: s = "abcabcababcc" Output: true Explanation: "" -> " abc " -> "abc abc " -> "abcabc abc " -> "abcabcab abc c" Thus, "abcabcababcc" is valid. Example 3: In

https://leetcode.com/problems/minimum-time-visiting-all-points/ On a plane there are  n  points with integer coordinates  points[i] = [xi, yi] . Your task is to find the minimum time in seconds to visit all points. You can move according to the next rules: In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second). You have to visit the points in the same order as they appear in the array.   Example 1: Input: points = [[1,1],[3,4],[-1,0]] Output: 7 Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0] Time from [1,1] to [3,4] = 3 seconds Time from [3,4] to [-1,0] = 4 seconds Total time = 7 seconds Example 2: Input: points = [[3,2],[-2,2]] Output: 5   Constraints: points.length == n 1 <= n <= 100 points[i].length == 2 -1000 <= points[i][0], points[i][1] <= 1000 ---- Intuition Min dist i

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/ Given two binary search trees  root1  and  root2 . Return a list containing  all the integers  from  both trees  sorted in  ascending  order.   Example 1: Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4] Example 2: Input: root1 = [0,-10,10], root2 = [5,1,7,0,2] Output: [-10,0,0,1,2,5,7,10] Example 3: Input: root1 = [], root2 = [5,1,7,0,2] Output: [0,1,2,5,7] Example 4: Input: root1 = [0,-10,10], root2 = [] Output: [-10,0,10] Example 5: Input: root1 = [1,null,8], root2 = [8,1] Output: [1,1,8,8]   Constraints: Each tree has at most  5000  nodes. Each node's value is between  [-10^5, 10^5] . ---- Intuition BST's inOrder is ascending Traverse both trees leftMost first to get to start point of both, save nodes in a stack while any of the stack is not empty pick up the non empty stack or pick the stack with lower peek value add node.val to ans Traverse leftmost on node.right --- Time - O(M

https://leetcode.com/problems/matrix-block-sum/ Given a  m * n  matrix  mat  and an integer  K , return a matrix  answer  where each  answer[i][j]  is the sum of all elements  mat[r][c]  for  i - K <= r <= i + K, j - K <= c <= j + K , and  (r, c)  is a valid position in the matrix.   Example 1: Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1 Output: [[12,21,16],[27,45,33],[24,39,28]] Example 2: Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2 Output: [[45,45,45],[45,45,45],[45,45,45]]   Constraints: m == mat.length n == mat[i].length 1 <= m, n, K <= 100 1 <= mat[i][j] <= 100 --- Intuition Similar to prefix sum for 1D, compute prefix sum for 2D array Prevent double counting sum[r][c] = mat[r][c] + sum[r - 1][c] + sum[r][c - 1] - sum[r - 1][c - 1] With prefix sum, calculate boundaries of box, keep bounds check r1 = max(r - k, 0) c1 = max(c - k, 0) r2 = min(r + k, R) c2 = min(c + k, C) with bounds check ans[r][c] = sum[r2][c2] - sum[r1 - 1][c2] - sum[r2][c1 - 1] + s

https://leetcode.com/problems/as-far-from-land-as-possible/ Given an N x N  grid  containing only values  0  and  1 , where  0  represents water and  1  represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance. The distance used in this problem is the  Manhattan distance : the distance between two cells  (x0, y0)  and  (x1, y1)  is  |x0 - x1| + |y0 - y1| . If no land or water exists in the grid, return  -1 .   Example 1: Input: [[1,0,1],[0,0,0],[1,0,1]] Output: 2 Explanation: The cell (1, 1) is as far as possible from all the land with distance 2. Example 2: Input: [[1,0,0],[0,0,0],[0,0,0]] Output: 4 Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.   Note: 1 <= grid.length == grid[0].length <= 100 grid[i][j]  is  0  or  1 ---- Intuition Shortest path => BFS, when exiting at first match Longest path => BFS, so that we can count levels, and exit till q is Empty Instead of

https://leetcode.com/problems/contains-duplicate-ii/ Given an array of integers and an integer  k , find out whether there are two distinct indices  i  and  j  in the array such that  nums[i] = nums[j]  and the  absolute  difference between  i  and  j  is at most  k . Example 1: Input: nums = [1,2,3,1] , k = 3 Output: true Example 2: Input: nums = [1,0,1,1] , k = 1 Output: true Example 3: Input: nums = [1,2,3,1,2,3] , k = 2 Output: false --- Intuition To achieve linear O(N) complexity, scan from L to R.. do not sort Save elements in a set if set.size() > k     remove nums[i - k - 1] if set.contains(nums[i])     return true set.add(nums[i]) --- Time - O(N) Space - O(K) --- Related problems 217-contains-duplicate ---

https://leetcode.com/problems/accounts-merge/ Given a list  accounts , each element  accounts[i]  is a list of strings, where the first element  accounts[i][0]  is a  name , and the rest of the elements are  emails  representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name. After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails  in sorted order . The accounts themselves can be returned in any order. Example 1: Input: accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", &

https://leetcode.com/problems/powx-n/ Implement  pow( x ,  n ) , which calculates  x  raised to the power  n  (x n ). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2 -2 = 1/2 2 = 1/4 = 0.25 Note: -100.0 <  x  < 100.0 n  is a 32-bit signed integer, within the range [−2 31 , 2 31  − 1] --- Intuition if pow < 0     pow = Math.abs(pow)     base = 1.0 / base Cast power to long to prevent against integer overflow when taking Math.abs while (pow > 0) {     pow = pow / 2; } Above is log N complexity To compute power, square the number in every iteration - running calculation If power is odd, multiply answer with number one extra time --- Time - O(log N) Space - O(1) ---