Today I solved the following problems from Striver DSA sheet. Also today I was able to figure out a dynamic programming solution on my own so I am very psyched about it.
PROBLEM 1: Search in a 2-D matrix: Took some time, but was able to figure out the most optimal approach, O(log(rows * log(cols))
PROBLEM 2: Implement pow function: Solved it optimally in O(log(n))
PROBLEM 3: Majority Element I: Was able to figure out O(N) time and space solution but learnt about Bayers' Voting Algorithm to reduce space to O(1)
PROBLEM 4: Majority Element II: Almost same concept as previous
PROBLEM 5: Reverse Pairs: Had solved 'Count Inversions' yesterday, hence was able to solve it on my own.
PROBLEM 6: Unique Paths: First solved it using DFS approach which had exponential time complexity. Then was able to boil it down to O(m * n) using memoization dynamic programming on the recursion.
Top comments (0)