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

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

LeetCode RaviTeja   11:30:00 PM

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

LeetCode cheatsheet

LeetCode cheatsheet

LeetCode RaviTeja   10:38:00 PM

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%

LeetCode 36. Valid Sudoku - Solution Beats 92.52%

LeetCode RaviTeja   10:07:00 PM

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

Solution    : https://leetcode.com/problems/valid-sudoku/solutions/3572587/92ms-beats-92-52-python-36-valid-sudoku-28-may-2023/

Submisson    : https://leetcode.com/problems/valid-sudoku/submissions/

Github code    :    https://github.com/ravivanjarapu/ProblemSolving/blob/main/LeetCode/36.%20Valid%20Sudoku.py

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/

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