Leetcode Problem 900-999

931. Minimum Falling Path Sum 🌟🌟

Recursion (TLE)

• For an element we can go down, right diagonal, or left diagonal, we will take minimum of those 3 and add with current element.
• The base case here is: If we reach to last row, we will return the current element.
• Also we have to check if the element is out of bound, if it is then return INT_MAX, because we are taking minimum element.

Memoization (AC)

• The recursive solution calculate same subproblem multiple times.
• we can use memoization table to store the results of the subproblems.
• If the subproblem is already calculated then return it else calculate and store it.
• TC: O(m*n)
• SC: O(m*n)

Tabulation (AC)

• we fill the first row with original values.
• then we fill rest as:
  • for first col we take min(up,upRightDig) + currElem
  • for last col we take min(up,upLeftDig) + currElem
  • for all other cols we take min(up,upLeftDig,upRightDig) + currElem
• Then we find the min of the last row.
• TC: O(m*n)
• SC: O(m*n)

---

938. Range Sum of BST 🌟

Traversal Approaches

• We can solve this problem with any of the traversal for the tree.
• We just need to check for the condition of the node value and then add the value to the sum.

BST Traversal

• We can use BST properties and avoid extra recursive calls.
• TC: O(N), N is number of nodes in the tree.
• SC: O(h), h is the height of the tree.

---

946. Validate Stack Sequences 🌟🌟

---

977. Squares of a Sorted Array 🌟

O(NlogN) Time solution

• Create new array and push_back squares of each element in it.
• Sort the new array.
• Return the new array.

O(N) Time solution

• We use two pointer method to solve this problem.
• set two array l=0 and r=arr.size()-1.
• traverse through the array and set max abs values square at last position.
• return the array.

---

980. Unique Paths III 🌟🌟🌟

DFS + Backtracking

• Below solution is explained in this video also on must read no-1.
• We don’t need zero++ for backtracking, because it is local variable.

MUST READ

• [Java Easy Solution

  DFS + Backtracking

  Explanation (Simplified)](https://leetcode.com/problems/unique-paths-iii/discuss/1553873/Java-Easy-Solution-oror-DFS-%2B-Backtracking-oror-Explanation-(Simplified))

• C++ Simple and Clean DFS Solution, Explained, 0ms Faster than 100%

---

986. Interval List Intersections 🌟🌟

2-pointer Solution

• [Python] Two Pointer Approach + Thinking Process Diagrams

---

989. Add to Array-Form of Integer 🌟

O(N) Time and O(1) Space

• We use k itself as carry.
• From last to first we fill array with addition and mod.
• If after loop, k have some carry we insert k to the start of array until it becomes 0.

---

991. Broken Calculator 🌟🌟

Greedy Solution

• Very intuitive solution. we can just think reverse of the problem statement.
• we will start from target and divide it when it is even else add one init, until target is greater than the starting value.
• count the total number of times we have to do so.
• return count + (startValue - target).
• TC: O(log target)
• TC: O(1)

---

994. Rotting Oranges 🌟🌟

BFS solution

• simple application of bfs.
• Watch Striver’s short video for better explanation.
• Time complexity: O(M*N)

---

997. Find the Town Judge 🌟

Most intuitive

• There are 2 main conditions for the town judge if it exists.
  • 1. The town judge trusts no one.
  • 1. Everyone (except the town judge)(n-1 people) trusts the town judge.
• So we can build trusts array in which we store how many person , the current person trusts.
• also we can build trusted array in which we store the current person is trusted by how many people.
• So the answer will be simple, if any person has trusts count == 0 and trusted count == n-1(everyone except town judge), then it is the town judge.else we return -1.
• TC: O(N)
• SC: O(N), 2 Extra vectors, We can also take vector of pairs

---