Tuesday, May 30, 2023

LeetCode 739 Daily temperatures solution - O(1) space O(n) time



The solution is same as LC's official editorial Approach 2: Array, Optimized Space

Below is my explanation in detailed manner.

The problem statement asks for finding the number of days you have to wait until a warmer temperature, given a list of daily temperatures.

Here's how the code work without using monotonic stack:

  1.  Initialize variables: 
    • `n` represents the length of the input list `temperatures`
    • `hottest` keeps track of the highest temperature encountered so far.
    • `answer` is initialized as a list of zeros with the same length as `temperatures`. It will store the result.
  2. Iterate over the `temperatures` list in reverse order:
    • Starting from the last day (`n - 1`) and going backwards to the first day (`0`), we process each day one by one.
  3. Check if the current day's temperature is greater than or equal to the `hottest` temperature encountered so far:
    •  If it is, update the `hottest` temperature to the current day's temperature and continue to the next iteration since there won't be any warmer days after this.
  4. If the current day's temperature is not hotter than the `hottest` temperature, we need to find the next warmer day:
    • Initialize `days` as `1` since at least one day is required to be warmer than the current day.
    • Use a while loop to increment `days` and check the temperatures of subsequent days (`temperatures[curr_day + days]`).
    • If the temperature of the subsequent day is still lower or equal to the current day's temperature, it means we haven't found a warmer day yet. In this case, we add the number of days needed to reach the warmer day (`answer[curr_day + days]`) to `days` and continue the while loop.
    • Once we find a warmer day, we update `answer[curr_day]` with the number of days (`days`) needed to reach that warmer day.
  5. After the loop completes, we have processed all days, and `answer` contains the number of days to wait until a warmer temperature for each day in the input list.
  6. Return the `answer` list, which holds the results.

The time complexity of this solution is O(n), where n is the length of the input list `temperatures` and constant space which is O(1) complexity.

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
hottest = 0
answer = [0] * n

for curr_day in range(n - 1, -1, -1):
current_temp = temperatures[curr_day]
if current_temp >= hottest:
hottest = current_temp
continue

days = 1
while temperatures[curr_day + days] <= current_temp:
# Use information from answer to search for the next warmer day
days += answer[curr_day + days]
answer[curr_day] = days

return answer


If you enjoyed this post, make sure you subscribe to my RSS feed! Comments are encouraged

Sunday, May 28, 2023

LeetCode cheatsheet

P𝗋𝗈𝖻𝗅𝖾𝗆 S𝗈𝗅𝗏𝗂𝗇𝗀 Tips

1. If an input array is sorted then
a. Binary search O(log n)
b. Two pointers O(n)

2. If asked for all permutations/subsets then
a. Backtracking (First preference)
b. Breadth First Search.

3. If given a tree or graphs then
a. DFS  (Preorder, Inorder, Postorder): O(n)
b. BFS (Level Order): O(n)

4. If Binary search tree:
a. - Left < Cur < Right: O(log n)
b. - Inorder Traversal visits the nodes in ascending (sorted) order: O(n
5. If given a linked list then
a. Two pointers

6. If recursion is banned then
a.   Convert to iterative solution using Stack

7. If must solve in-place then
a. Swap corresponding values
b. Store one or more different values in the same pointer

8. If asked for maximum/minimum subarray/subset/options then
a. Dynamic programming

9. If asked for top/maximum/minimum/closest/least K items then
a. Heap

10. If asked for common strings among a set of strings
a. Hash Map
b. Trie

11. If we need to search/manipulate a bunch of strings:
a. Trie

12. For a problem involving arrays, if there exists a solution in O(n^2) time and O(1) space, there                  must exist two other solutions:
a. Use a HashMap or a Set for O(n) time and O(n) space
b. Sort input for O(n log n) time and O(1) space

13. Else
a. Use a HashMap or a Set for O(n) time and O(n) space
                Sort input for O(n log n) time and O(1) space








If you enjoyed this post, make sure you subscribe to my RSS feed! Comments are encouraged

LeetCode 36. Valid Sudoku - Solution Beats 92.52%


Problem    https://leetcode.com/problems/valid-sudoku/



Intuition

Compare the list with set. If lengths are same, they are unique.

Approach

  1. Exclude '.' and check if every row list length is same when compared with its set
  2. Transpose the matrix and repeat above for all columns check
  3. Take each 3x3 sub-matrix and convert to list. Compare the list with its set

Complexity

  • Time complexity: O(3 n^2) --> O(n^2)

  • Space complexity: O(9) --> O(1). Please correct me if I am wrong.

Proof:
Submission link: https://leetcode.com/problems/valid-sudoku/submissions/837321916/

36 Valid Sudoku.jpg

Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        if not board:
            return False
        for row in board:
            temp = [i for i in row if i != '.']
            if len(set(temp)) != len(temp):
                return False

        transpose_dict = defaultdict(list)
        for row in board:
            for i in range(len(row)):
                if row[i] != '.':
                    transpose_dict[i].append(row[i])
        for k, v in transpose_dict.items():
            if len(v) != len(set(v)):
                return False

        for i in range(0, len(board), 3):
            for j in range(0, len(board), 3):
                box = []
                for k in range(i, i + 3):
                    box.extend(board[k][j:j + 3])

                box = [element for element in box if element != '.']
                if len(box) != len(set(box)):
                    return False
        return True



If you enjoyed this post, make sure you subscribe to my RSS feed! Comments are encouraged