Leetcode Problem 500-599

---

501. Find Mode in Binary Search Tree 🌟

Hash map with DFS

• Traverse all the tree and store frequency of each node in a hash map.
• Get the highest frequency and return vector with all elements with that frequency.
• TC: O(N^2)
• SC: O(N)

Iterative DFS

• Same as above but iterative DFS.

Without extra space(without Hashmap)

• Just little modification in inorder traversal.
• Keep track of previous node, current frequency and max frequency.
• Every time we encounter a new node, check if it is equal to previous node, if yes, increment current frequency, else reset it to 1.
• If current frequency is equal to max frequency, add it to result vector, else if current frequency is greater than max frequency, clear the result vector and add current node to it and update max frequency.
• TC: O(N)
• SC: O(1), if we don’t consider the result vector and recursion stack.

Morris Traversal

• TC: O(N)
• SC: O(1)

Coming Soon …

TODO: solve using morris traversal.

---

515. Find Largest Value in Each Tree Row 🌟🌟

This question is in continuation with A general approach to level order traversal questions series.

Previous Questions

1. Binary tree level order traversal
2. Binary tree level order traversal - II
3. Binary tree zig-zag level order traversal
4. Average of levels
5. Binary tree right side view

Recursive Solution

• Self explanatory

Iterative solution

• self explanatory

---

518. Coin Change 2 🌟🌟

Recursive Solution (TLE)

• For a i’th coin in coins, we can either use it or not use it.
• If the ith coin is less than or equal to the amount, we can use it or not use it.
• else, ith coin is greater than amount we cannot use it.
• Since we want to find the number of combinations, we add both include and exclude the ith coin.

Memoization (AC)

• The recursive solution calculates same sub-problem multiple times.
• We can use memoization to avoid this.
• TC: O(N * amount)
• SC: O(N * amount)

Tabulation (AC)

• Iterative DP.
• TC: O(N * amount)
• SC: O(N * amount)

---

523. Continuous Subarray Sum 🌟🌟

Brute force

• Try all possible subarrays and check if the sum is a multiple of k.
• Will give TLE.
• TC: O(n^2)

Prefix sum with hash map

• The intuition is that if we take remainder of subarray A[i:j] with k, and remainder of B[i:j+x] and they both have same remainder, then subarray between j and j+x will have remainder 0.
• Ex. 23, 2, 4, 6, 7 - here 23 have remainder 5 and 23+2+4 also have remainder 5. So, subarray 2,4 have remainder 0.
• So we can store indexes of all the remainders that we encounter and if remainder repeats and it has size more than or equal to 2 then we can return true.
• We can store 0’s index as -1 to handle the case when first 2 elements have remainder 0.
• Else return false.
• TC: O(n)
• SC: O(n)

---

525. Contiguous Array 🌟🌟

Brute Force (TLE)

• We will try all subarrays, and count the number of zeros and ones in each subarray.
• When the number of zeros and ones are equal, that means we can update our max count.
• Time Complexity: O(n^2)
• Space Complexity: O(1)

hashmap (AC)

• We can optimize brute force with hashmap.
• We increment the count by 1 if num is 1 and decrement count by 1 if num is 0.
• If the count is 0, we know that the subarray from index i to j is a contiguous subarray with equal number of 0s and 1s.
• TC: O(N)
• SC: O(N)

READ MORE

• [[C++] Simplest Solution

  Optimization from Brute Force

  One-Pass]](https://leetcode.com/problems/contiguous-array/discuss/1743341/C%2B%2B-Simplest-Solution-or-Optimization-from-Brute-Force-or-One-Pass)

---

532. K-diff Pairs in an Array 🌟🌟

Brute force

• We can traverse every pair of array elements and check if the difference is k.
• inset the minimum value in the set and return set.size().
• TC: O(n^2)
• SC: O(n)

with binary search

• we can sort the array and find the num+k in the sorted array.
• TC: O(nlogn)
• SC: O(n)

with hashmap

• we can reduce the time complexity if we store the count of numbers in hashmap.
• traverse the hash map.
  • if k>0 and map has num+x in it, increase the count.
  • if k==0 and num has frequency greater then 1, increase the count
• return count.
• TC: O(n)
• SC: O(n)

---

540. Single Element in a Sorted Array 🌟🌟

Brute force

• check for duplicates element using 2for loops.
• TC: O(N^2)
• SC: O(1)

Hashmap

• use hashmap to store the frequency of each element.
• in hashmap if frequency is 1 then return the element.
• TC: O(N)
• SC: O(N)

linear search

• We can linearly search the array for the element.
• for each time we increment the i by 2 and check for adjacent elements.
• if the element is not equal to the previous element then we return the current element.
• TC: O(N)
• SC: O(1)

Bit Manipulation(XOR)

• We know that xor of 2 same numbers is 0.In the question it is given that all number except the ans appear twice.
• So we can use XOR to find the ans.
• TC: O(N)
• SC: O(1)

Binary Search

• We can observe that before unique elements every repeated element starts with even index and after unique elements every repeated element starts with odd index.
• so we can just binary search the ans based on the even and odd indexes.
• TC: O(logN)
• SC: O(1)

---

---

542. 01 Matrix 🌟🌟

BFS solution

• Firstly, we can see that the distance of all zero-cells are 0.
• Same idea with Topology Sort, we process zero-cells first, then we use queue data structure to keep the order of processing cells, so that cells which have the smaller distance will be processed first. Then we expand the unprocessed neighbors of the current processing cell and push into our queue.
• After all, we can achieve the minimum distance of all cells in our matrix.

Complexity:

• Time: O(M * N), where M is number of rows, N is number of columns in the matrix.
• Space: O(M * N), space for the queue.

DP Solution

• Firstly, we can see that the distance of all zero-cells are 0, so we skip zero-cells, we process one-cells only.
• In DP, we can only use previous values if they’re already computed.
• In this problem, a cell has at most 4 neighbors that are left, top, right, bottom. If we use dynamic programming to compute the distance of the current cell based on 4 neighbors simultaneously, it’s impossible because we are not sure if distance of neighboring cells is already computed or not.
• That’s why, we need to compute the distance one by one:
  • Firstly, for a cell, we restrict it to only 2 directions which are left and top. Then we iterate cells from top to bottom, and from left to right, we calculate the distance of a cell based on its left and top neighbors.
  • Secondly, for a cell, we restrict it only have 2 directions which are right and bottom. Then we iterate cells from bottom to top, and from right to left, we update the distance of a cell based on its right and bottom neighbors.

Complexity:

• Time: O(M * N), where M is number of rows, N is number of columns in the matrix.
• Space: O(1)

---

547. Number of Provinces 🌟🌟

---

551. Student Attendance Record I 🌟

Iterative Solution

• We count ‘A’ and ‘L’ from the string.
• If at any point we break the chain of consecutive ‘L’ we set lCnt=0.
• If count of ‘A’ exceeds 1 or count of ‘L’ = 3 we return false, else true.
• TC: O(N), Where n is length of the string.
• SC: O(1), No extra space required.

Using Builtin Functions

• We can get same results with inbuilt functions of C++ STL.

Recursive Solution

• Code is self explanatory.
• TC: O(N), Where n is length of string.
• SC: O(N), Recursive stack space.

557. Reverse Words in a String III 🌟

O(N*M) Time and O(M) Space

• We can use stack to reverse each word.
• Traverse the string and push each character in the stack until we encounter a space.
• if space is encountered, empty the stack by popping the top character and append it to the result string.

---

560. Subarray Sum Equals K 🌟🌟

Brute force (TLE)

• We can find all subarrays and count subarrays with sum equal to k.
• TC: O(n^3)
• SC: O(1)

prefix sum (TLE)

• Better Brute Force.
• In the 3rd loop we are finding the sum of the subarray.
• We can optimize 3rd loop by prefix sum.
• Store the prefix sum of array elements.
• While traversing array if(prefix[j] - prefix[i]==k) increment the count.
• return the count.
• TC: O(n^2)
• SC: O(n)

Running sum (TLE)

• Instead of using prefix array to store the prefix sum, we can find the running sum.
• If sum=k increment the count.
• Return the count.
• TC: O(n^2)
• SC: O(1)

Using hashmap (AC)

• Below explanation is from LeetCode Discuss.

• Consider the below example: array : 3 4 7 -2 2 1 4 2 presum : 3 7 14 12 14 15 19 21 index : 0 1 2 3 4 5 6 7 k = 7 Map should look like : (0,1) , (3,1), (7,1), (14,2) , (12,1) , (15,1) , (19,1) , (21,1)

• Consider 21(presum) now what we do is sum-k that is 21-7 = 14. Now we will check our map if we go by just count++ logic we will just increment the count once and here is where we go wrong.

• When we search for 14 in presum array we find it on 2 and 4 index. The logic here is that 14 + 7 = 21 so the array between indexes -> 3 to 7 (-2 2 1 4 2) -> 5 to 7 both have sum 7 ( 1 4 2) The sum is still 7 in this case because there are negative numbers that balance up for. So if we consider count++ we will have one count less as we will consider only array 5 to 7 but now we know that 14 sum occured earlier too so even that needs to be added up so map.get(sum-k).

• Another way of understanding this is that if there is increase of k in the presum array we have found a new subarray so that is why we look for currentSum-k.
• TC: O(n)
• SC: O(n)

---

566. Reshape the Matrix 🌟

O(N*M) Time and O(N*M)+O(N*M) Space

• naive approach
• store 2D array in 1D temporary array.
• Create new r*c matrix and fill it with the values from the temporary array.

O(N*M) Time and O(N*M) Space (Row-First Approach

• M[i] => M[i/n][i%n] it will result in right mapping
• i/c will give us the row number of output matrix. We will move to New row after every c elements and thus dividing by c will give the row number.
• i%c will give us the column number of output matrix. We will be begin from start of new row after every c elements and this the remainder will give column of current row.
• The same happens in i/n and i%n but for the mat matrix).

O(N*M) Time and O(N*M) Space (Column-First Approach)

soon…

---

567. Permutation in String 🌟🌟

O(N) Time and O(1) Space

• Permutation of string is the anagram of itself.
• So, the problem become, find the anagram of the string1 in the string2.
• We can find it with maintaining two frequency arrays for s1 and s2.
• If at any point their frequencies are equal, then return true.
• else by maintaining window size(s1.size()), try for next substring.
• finally, return false, because there is no anagram of string1 in string2.

---

576. Out of Boundary Paths 🌟🌟

Recursion (TLE)

• Trivial DFS: travel in all 4 directions.
• If we hit the boundary return 1.
• If we don’t have any moves to perform , return 0;
• TC: O(4^maxMove)
• SC: O(maxMove)

Memorization (AC)

• Use memoization to avoid redundant calculations.
• TC: O(n*m*maxMove)
• SC: O(n*m*maxMove)

Tabulation (Bottom-Up) (AC)

• Memoization to tabulation conversion.
• TC: O(n*m*maxMove)
• SC: O(n*m*maxMove)
• isOutOfBounds() function returns true if the current position is out of bounds, found this trick in discussion tab.

---