Leetcode Problem 1200-1299

1200. Minimum Absolute Difference 🌟

Brute force

• First we find the minimum difference between all the pairs of array.
• With brute force, we can find all pairs of elements with the minimum absolute difference of any two elements in O(n^2) time.
• TC: O(N^2)
• SC: O(1)

Sort + Two traversal

• We sort the array first.
• Then we traverse the array from the beginning to the end and find minimum difference.
• Since array is sorted minimum difference pairs will be adjacent elements of the array.
• store them in 2D ans vector and return ans.
• TC: O(NlogN): For sorting

• **SC: O(logN)

  O(N)**: Space required for internal sorting. in C++ its O(logN) for py its O(N).

---

1232. Check If It Is a Straight Line 🌟

Solution

• We can check if the slope of any two points is equal or not.
• If the slope is equal, then the points are on the same line.
• Slope = (y2 - y1) / (x2 - x1) = dy / dx, where dy = y2 - y1, dx = x2 - x1
• For line to be straight, slope of any two points should be equal, i.e. ` => (y3-y1)/(x3-x1) = (y2-y1)/(x2-x1) => (y3-y1)(x2-x1) = (y2-y1)(x3-x1) => dx(y3-y1) = dy(x3-x1)`
• So we need to check if dy*(x3-x1) = dx*(y3-y1) for all points.
• TC: O(N)
• SC: O(1)

---

1286. Iterator for Combination 🌟🌟

Prerequisites:

• Backtracking Concept
• 77. Combinations

Backtracking Solution (Efficient)

• First, in the initialization, we recompute all the combinations of given string , and store the string of combinationLength in the combination vector. It will be done in O(2^n) time and also in Dictionary order.
• In the next() function, from the combination vector, we return the next combination.
• In the hasNext() function, we check if the combination vector has the next combination or not.

Bitmasking Solution (Not more efficient)

• Here change is, we use bitmasking to compute all the combinations. takes O(2^n) time.
• but we need to have additional map to store the combinations in sorted order. takes O(log N) time.

---

1289. Minimum Falling Path Sum II 🌟🌟🌟

Recursion (TLE)

• From every element in the first row of grid we find min answer.
• we have to try all the columns except the current column in the recursion and get the minimum answer.
• When we reach the last row, return the element itself.
• also check for out of bounds.

Memoization

• We use memoization table to store the result of subproblems.
• We can return directly from the table if the computation is already done, else we store new computation.

Tabulation (AC)

• The memoization solution can be converted into tabulation.

---

1295. Find Numbers with Even Number of Digits 🌟

O(N*length(num)) Time and O(1) Space

• Implementation.

O(N) Time and O(1) Space

• Using log10(num) to find the length of the number.
• log10(num) gives length(num)-1.

---