LeetCode

This post is used to log my leetcode problem solving.

2785. Sort Vowels in a String 2025.09.11

Given a 0-indexed string s, permute s to get a new string t such that:

• All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
• The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

Return the resulting string.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

Example 1:

Input: s = “lEetcOde”
Output: “lEOtcede”
Explanation: ‘E’, ‘O’, and ’e’ are the vowels in s; ’l’, ’t’, ‘c’, and ’d’ are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

Example 2:

Input: s = “lYmpH”
Output: “lYmpH”
Explanation: There are no vowels in s (all characters in s are consonants), so we return “lYmpH”.

Constraints:

• 1 <= s.length <= 105
• s consists only of letters of the English alphabet in uppercase and lowercase.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution(object):
    def sortVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = list(s)

        vowels = ['A','E','I','O','U','a','e','i','o','u']
        vowel_indice = []
        vowel_counts = [0] * len(vowels)

        for i,char in enumerate(s):
            if char in vowels:
                vowel_counts[vowels.index(char)] += 1
                vowel_indice.append(i)

        for i,char in enumerate(vowels):
            start_index = sum(vowel_counts[:i]) if i else 0
            end_index = sum(vowel_counts[:i+1])
            for idx in range(start_index, end_index):
                s[vowel_indice[idx]] = char

        return "".join(s)

3227. Vowels Game in a String 2025.09.12

Alice and Bob are playing a game on a string.

You are given a string s, Alice and Bob will take turns playing the following game where Alice starts first:

• On Alice’s turn, she has to remove any non-empty substring from s that contains an odd number of vowels.
• On Bob’s turn, he has to remove any non-empty substring from s that contains an even number of vowels.

The first player who cannot make a move on their turn loses the game. We assume that both Alice and Bob play optimally.

Return true if Alice wins the game, and false otherwise.

The English vowels are: a, e, i, o, and u.

Example 1:

Input: s = “leetcoder”

Output: true

Explanation:
Alice can win the game as follows:

• Alice plays first, she can delete the underlined substring in s = "**leetco**der" which contains 3 vowels. The resulting string is s = "der".
• Bob plays second, he can delete the underlined substring in s = "**d**er" which contains 0 vowels. The resulting string is s = "er".
• Alice plays third, she can delete the whole string s = "**er**" which contains 1 vowel.
• Bob plays fourth, since the string is empty, there is no valid play for Bob. So Alice wins the game.

Example 2:

Input: s = “bbcd”

Output: false

Explanation:
There is no valid play for Alice in her first turn, so Alice loses the game.

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters.

Solution

Consider only the number of vowels. If the number of vowels is 0, Alice fails. If it’s odd, Alice could remove the whole string, Alice wins. If it’s even, after removing odd number of vowels, the remaining number is odd, Alice wins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution(object):
    def doesAliceWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        vowels = 'aeiou'
        for char in s:
            if char in vowels:
                return True
        return False

3541. Find Most Frequent Vowel and Consonant 2025.09.13

You are given a string s consisting of lowercase English letters ('a' to 'z').

Your task is to:

• Find the vowel (one of 'a', 'e', 'i', 'o', or 'u') with the maximum frequency.
• Find the consonant (all other letters excluding vowels) with the maximum frequency.

Return the sum of the two frequencies.

Note: If multiple vowels or consonants have the same maximum frequency, you may choose any one of them. If there are no vowels or no consonants in the string, consider their frequency as 0.

The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: s = “successes”

Output: 6

Explanation:

• The vowels are: 'u' (frequency 1), 'e' (frequency 2). The maximum frequency is 2.
• The consonants are: 's' (frequency 4), 'c' (frequency 2). The maximum frequency is 4.
• The output is 2 + 4 = 6.

Example 2:

Input: s = “aeiaeia”

Output: 3

Explanation:

• The vowels are: 'a' (frequency 3), 'e' ( frequency 2), 'i' (frequency 2). The maximum frequency is 3.
• There are no consonants in s. Hence, maximum consonant frequency = 0.
• The output is 3 + 0 = 3.

Constraints:

• 1 <= s.length <= 100
• s consists of lowercase English letters only.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    def maxFreqSum(self, s):
        """
        :type s: str
        :rtype: int
        """
        freqs = [0] * 26
        for char in s:
            freqs[ord(char)-ord('a')] += 1

        vowel_indice = [ord(i)-ord('a') for i in 'aeiou']
        vowel_freqs = [freqs[i] for i in vowel_indice]
        conson_freqs = [freqs[i] for i in range(26) if i not in vowel_indice]
        return max(vowel_freqs) + max(conson_freqs)

966. Vowel Spellchecker 2025.09.14

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

• Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
  • Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
  • Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
  • Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
• Vowel Errors: If after replacing the vowels ('a', 'e', 'i', 'o', 'u') of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
  • Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
  • Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
  • Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

• When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
• When the query matches a word up to capitlization, you should return the first such match in the wordlist.
• When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
• If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = [“KiTe”,“kite”,“hare”,“Hare”], queries = [“kite”,“Kite”,“KiTe”,“Hare”,“HARE”,“Hear”,“hear”,“keti”,“keet”,“keto”] Output: [“kite”,“KiTe”,“KiTe”,“Hare”,“hare”,"","",“KiTe”,"",“KiTe”]

Example 2:

Input: wordlist = [“yellow”], queries = [“YellOw”] Output: [“yellow”]

Constraints:

• 1 <= wordlist.length, queries.length <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] and queries[i] consist only of only English letters.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution(object):
    def spellchecker(self, wordlist, queries):
        """
        :type wordlist: List[str]
        :type queries: List[str]
        :rtype: List[str]
        """
        def vowel_error(word1, word2):
            if len(word1) != len(word2):
                return False
            for i in range(len(word1)):
                if word1[i].lower() != word2[i].lower():
                    if word1[i].lower() in "aeiou" and word2[i].lower() in "aeiou":
                        continue
                    else:
                        return False
            return True
        
        match_map = dict()
        for query in queries:
            for word in wordlist:
                if word.lower() == query.lower() or vowel_error(query, word):
                    match_map.setdefault(query, []).append(word)
        res = []
        for k in queries:
            v = match_map.get(k, [])
            if not v:
                res.append("")
            elif len(v) == 1:
                res.append(v[0])
            else:
                if k in v:
                    res.append(k)
                else:
                    flag = False
                    for i in v:
                        if i.lower() == k.lower():
                            res.append(i)
                            flag = True
                            break
                    if not flag:
                        for i in v:
                            if vowel_error(i, k):
                                res.append(i)
                                break
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

class Solution(object):
    def spellchecker(self, wordlist, queries):
        """
        :type wordlist: List[str]
        :type queries: List[str]
        :rtype: List[str]
        """
        
        # Helper function to create a "devoweled" version of a word.
        # Example: "Kite" -> "k*t*"
        def devowel(word):
            vowels = "aeiou"
            # Replace each vowel with a placeholder '*'
            return "".join('*' if char in vowels else char for char in word.lower())

        # --- Step 1: Pre-process the wordlist into fast-lookup maps ---

        # For exact matches (Priority 1)
        exact_words = set(wordlist)
        
        # For case-insensitive matches (Priority 2)
        # Maps a lowercase word to its first occurrence in the original wordlist.
        case_map = {}
        
        # For vowel-error matches (Priority 3)
        # Maps a devoweled word to its first occurrence in the original wordlist.
        vowel_map = {}

        for word in wordlist:
            lower_word = word.lower()
            devoweled_word = devowel(word)
            
            # setdefault only sets the value if the key is not already present.
            # This correctly handles the "first occurrence" rule.
            case_map.setdefault(lower_word, word)
            vowel_map.setdefault(devoweled_word, word)
            
        # --- Step 2: Process queries using the maps ---
        
        result = []
        for query in queries:
            # Rule 1: Check for an exact match
            if query in exact_words:
                result.append(query)
                continue
            
            lower_query = query.lower()
            
            # Rule 2: Check for a case-insensitive match
            if lower_query in case_map:
                result.append(case_map[lower_query])
                continue
                
            devoweled_query = devowel(query)
            
            # Rule 3: Check for a vowel-error match
            if devoweled_query in vowel_map:
                result.append(vowel_map[devoweled_query])
                continue
            
            # Rule 4: No match found
            result.append("")
            
        return result

1935. Maximum Number of Words You Can Type 2025.09.15

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = “hello world”, brokenLetters = “ad” Output: 1 Explanation: We cannot type “world” because the ’d’ key is broken.

Example 2:

Input: text = “leet code”, brokenLetters = “lt” Output: 1 Explanation: We cannot type “leet” because the ’l’ and ’t’ keys are broken.

Example 3:

Input: text = “leet code”, brokenLetters = “e” Output: 0 Explanation: We cannot type either word because the ’e’ key is broken.

Constraints:

• 1 <= text.length <= 104
• 0 <= brokenLetters.length <= 26
• text consists of words separated by a single space without any leading or trailing spaces.
• Each word only consists of lowercase English letters.
• brokenLetters consists of distinct lowercase English letters.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def canBeTypedWords(self, text, brokenLetters):
        """
        :type text: str
        :type brokenLetters: str
        :rtype: int
        """
        words = text.split()
        count = 0
        for word in words:
            flag = True
            for char in brokenLetters:
                if char in word:
                    flag = False
                    break
            if flag:
                count += 1
        return count

2197. Replace Non-Coprime Numbers in Array 2025.09.16

You are given an array of integers nums. Perform the following steps:

1. Find any two adjacent numbers in nums that are non-coprime.
2. If no such numbers are found, stop the process.
3. Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
4. Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 108.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

Example 1:

Input: nums = [6,4,3,2,7,6,2] Output: [12,7,6] Explanation:

• (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
• (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
• (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
• (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [12,7,6]. Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3] Output: [2,1,1,3] Explanation:

• (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
• (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
• (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [2,1,1,3]. Note that there are other ways to obtain the same resultant array.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• The test cases are generated such that the values in the final array are less than or equal to 108.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution(object):
    def replaceNonCoprimes(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a
        
        def lcm(a, b):
            return a * b / gcd(a, b)
        
        if len(nums) < 2:
            return nums

        def NonCoprime(nums):
            for i in range(len(nums)-1):
                if gcd(nums[i], nums[i+1]) > 1:
                    return False
            return True

        while not NonCoprime(nums):
            for i in range(len(nums)-1):
                if gcd(nums[i], nums[i+1]) > 1:
                    nums[i+1] = lcm(nums[i], nums[i+1])
                    nums[i] = None
            nums = [num for num in nums if num]
        
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution(object):
    def replaceNonCoprimes(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a
        
        def lcm(a, b):
            return a * b // gcd(a, b)  # Use integer division
        
        if len(nums) < 2:
            return nums
        
        stack = []
        
        for num in nums:
            stack.append(num)
            
            # Keep merging with the previous element while they're not coprime
            while len(stack) >= 2 and gcd(stack[-2], stack[-1]) > 1:
                # Pop the last two elements, compute their LCM, and push back
                b = stack.pop()
                a = stack.pop()
                stack.append(lcm(a, b))
        
        return stack

2353. Design a Food Rating System 2025.09.17

Design a food rating system that can do the following:

• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.

Implement the FoodRatings class:

• FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.
  • foods[i] is the name of the ith food,
  • cuisines[i] is the type of cuisine of the ith food, and
  • ratings[i] is the initial rating of the ith food.
• void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
• String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

Input [“FoodRatings”, “highestRated”, “highestRated”, “changeRating”, “highestRated”, “changeRating”, “highestRated”] [[[“kimchi”, “miso”, “sushi”, “moussaka”, “ramen”, “bulgogi”], [“korean”, “japanese”, “japanese”, “greek”, “japanese”, “korean”], [9, 12, 8, 15, 14, 7]], [“korean”], [“japanese”], [“sushi”, 16], [“japanese”], [“ramen”, 16], [“japanese”]]
Output
[null, “kimchi”, “ramen”, null, “sushi”, null, “ramen”]

Explanation FoodRatings foodRatings = new FoodRatings([“kimchi”, “miso”, “sushi”, “moussaka”, “ramen”, “bulgogi”], [“korean”, “japanese”, “japanese”, “greek”, “japanese”, “korean”], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated(“korean”); // return “kimchi”
// “kimchi” is the highest rated korean food with a rating of 9.
foodRatings.highestRated(“japanese”); // return “ramen”
// “ramen” is the highest rated japanese food with a rating of 14.
foodRatings.changeRating(“sushi”, 16); // “sushi” now has a rating of 16.
foodRatings.highestRated(“japanese”); // return “sushi”
// “sushi” is the highest rated japanese food with a rating of 16.
foodRatings.changeRating(“ramen”, 16); // “ramen” now has a rating of 16.
foodRatings.highestRated(“japanese”); // return “ramen”
// Both “sushi” and “ramen” have a rating of 16.
// However, “ramen” is lexicographically smaller than “sushi”.

Constraints:

• 1 <= n <= 2 * 104
• n == foods.length == cuisines.length == ratings.length
• 1 <= foods[i].length, cuisines[i].length <= 10
• foods[i], cuisines[i] consist of lowercase English letters.
• 1 <= ratings[i] <= 108
• All the strings in foods are distinct.
• food will be the name of a food item in the system across all calls to changeRating.
• cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.
• At most 2 * 104 calls in total will be made to changeRating and highestRated.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class FoodRatings(object):

    def __init__(self, foods, cuisines, ratings):
        """
        :type foods: List[str]
        :type cuisines: List[str]
        :type ratings: List[int]
        """
        self.foods = foods
        self.cuisines = cuisines
        self.ratings = ratings

    def changeRating(self, food, newRating):
        """
        :type food: str
        :type newRating: int
        :rtype: None
        """
        self.ratings[self.foods.index(food)] = newRating

    def highestRated(self, cuisine):
        """
        :type cuisine: str
        :rtype: str
        """
        idx = [i for i in range(len(self.cuisines)) if self.cuisines[i] == cuisine]
        max_rating = max(self.ratings[i] for i in idx)
        max_food = list()
        for i in idx:
            if self.ratings[i] == max_rating:
                max_food.append(self.foods[i])
        return min(max_food)

# Your FoodRatings object will be instantiated and called as such:
# obj = FoodRatings(foods, cuisines, ratings)
# obj.changeRating(food,newRating)
# param_2 = obj.highestRated(cuisine)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import heapq
class FoodRatings(object):

    def __init__(self, foods, cuisines, ratings):
        """
        :type foods: List[str]
        :type cuisines: List[str]
        :type ratings: List[int]
        """
        self.food_info = {}
        self.cuisines = {}
        for f,c,r in zip(foods, cuisines, ratings):
            self.food_info[f] = [c, r]
            if c not in self.cuisines:
                self.cuisines[c] = []
            heapq.heappush(self.cuisines[c], (-r, f))



    def changeRating(self, food, newRating):
        """
        :type food: str
        :type newRating: int
        :rtype: None
        """
        self.food_info[food][1] = newRating
        cuisine = self.food_info[food][0]
        heapq.heappush(self.cuisines[cuisine], (-newRating, food))


    def highestRated(self, cuisine):
        """
        :type cuisine: str
        :rtype: str
        """
        heap = self.cuisines[cuisine]
        while heap:
            rating, food = heap[0]
            rating = -rating
            if rating == self.food_info[food][1]:
                return food
            else:
                heapq.heappop(heap)


# Your FoodRatings object will be instantiated and called as such:
# obj = FoodRatings(foods, cuisines, ratings)
# obj.changeRating(food,newRating)
# param_2 = obj.highestRated(cuisine)

3408. Design Task Manager 2025.09.18

There is a task management system that allows users to manage their tasks, each associated with a priority. The system should efficiently handle adding, modifying, executing, and removing tasks.

Implement the TaskManager class:

• TaskManager(vector<vector<int>>& tasks) initializes the task manager with a list of user-task-priority triples. Each element in the input list is of the form [userId, taskId, priority], which adds a task to the specified user with the given priority.

• void add(int userId, int taskId, int priority) adds a task with the specified taskId and priority to the user with userId. It is guaranteed that taskId does not exist in the system.

• void edit(int taskId, int newPriority) updates the priority of the existing taskId to newPriority. It is guaranteed that taskId exists in the system.

• void rmv(int taskId) removes the task identified by taskId from the system. It is guaranteed that taskId exists in the system.

• int execTop() executes the task with the highest priority across all users. If there are multiple tasks with the same highest priority, execute the one with the highest taskId. After executing, the taskId is removed from the system. Return the userId associated with the executed task. If no tasks are available, return -1.

Note that a user may be assigned multiple tasks.

Example 1:

Input:
[“TaskManager”, “add”, “edit”, “execTop”, “rmv”, “add”, “execTop”]
[[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]

Output:
[null, null, null, 3, null, null, 5]

Explanation

TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // Initializes with three tasks for Users 1, 2, and 3.
taskManager.add(4, 104, 5); // Adds task 104 with priority 5 for User 4.
taskManager.edit(102, 8); // Updates priority of task 102 to 8.
taskManager.execTop(); // return 3. Executes task 103 for User 3.
taskManager.rmv(101); // Removes task 101 from the system.
taskManager.add(5, 105, 15); // Adds task 105 with priority 15 for User 5.
taskManager.execTop(); // return 5. Executes task 105 for User 5.

Constraints:

• 1 <= tasks.length <= 105
• 0 <= userId <= 105
• 0 <= taskId <= 105
• 0 <= priority <= 109
• 0 <= newPriority <= 109
• At most 2 * 105 calls will be made in total to add, edit, rmv, and execTop methods.
• The input is generated such that taskId will be valid.

Solution

Similar to last daily problem. Use a hashmap to store all tasks and a heap to store priority with lazy cleanup.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

import heapq
class TaskManager(object):

    def __init__(self, tasks):
        """
        :type tasks: List[List[int]]
        """
        self.tasks = dict()
        self.priority = list()
        for task in tasks:
            uid, tid, prio = task
            self.tasks[tid] = [uid, prio]
            heapq.heappush(self.priority, (-prio, -tid))

    def add(self, userId, taskId, priority):
        """
        :type userId: int
        :type taskId: int
        :type priority: int
        :rtype: None
        """
        self.tasks[taskId] = [userId, priority]
        heapq.heappush(self.priority, (-priority, -taskId))
        

    def edit(self, taskId, newPriority):
        """
        :type taskId: int
        :type newPriority: int
        :rtype: None
        """
        self.tasks[taskId][1] = newPriority
        heapq.heappush(self.priority, (-newPriority, -taskId))

    def rmv(self, taskId):
        """
        :type taskId: int
        :rtype: None
        """
        del self.tasks[taskId]

    def execTop(self):
        """
        :rtype: int
        """
        if not self.tasks:
            return -1
        while self.priority:
            prio, tid = heapq.heappop(self.priority)
            prio = -prio
            tid = -tid
            if tid in self.tasks and prio == self.tasks[tid][1]:
                uid = self.tasks[tid][0]
                del self.tasks[tid]
                return uid
            else:
                continue

        


# Your TaskManager object will be instantiated and called as such:
# obj = TaskManager(tasks)
# obj.add(userId,taskId,priority)
# obj.edit(taskId,newPriority)
# obj.rmv(taskId)
# param_4 = obj.execTop()

3484. Design Spreadsheet 2025.09.19

A spreadsheet is a grid with 26 columns (labeled from 'A' to 'Z') and a given number of rows. Each cell in the spreadsheet can hold an integer value between 0 and 105.

Implement the Spreadsheet class:

• Spreadsheet(int rows) Initializes a spreadsheet with 26 columns (labeled 'A' to 'Z') and the specified number of rows. All cells are initially set to 0.
• void setCell(String cell, int value) Sets the value of the specified cell. The cell reference is provided in the format "AX" (e.g., "A1", "B10"), where the letter represents the column (from 'A' to 'Z') and the number represents a 1-indexed row.
• void resetCell(String cell) Resets the specified cell to 0.
• int getValue(String formula) Evaluates a formula of the form "=X+Y", where X and Y are either cell references or non-negative integers, and returns the computed sum.

Note: If getValue references a cell that has not been explicitly set using setCell, its value is considered 0.

Example 1:

Input:
[“Spreadsheet”, “getValue”, “setCell”, “getValue”, “setCell”, “getValue”, “resetCell”, “getValue”]
[[3], ["=5+7"], [“A1”, 10], ["=A1+6"], [“B2”, 15], ["=A1+B2"], [“A1”], ["=A1+B2"]]

Output:
[null, 12, null, 16, null, 25, null, 15]

Explanation

Spreadsheet spreadsheet = new Spreadsheet(3); // Initializes a spreadsheet with 3 rows and 26 columns
spreadsheet.getValue("=5+7"); // returns 12 (5+7)
spreadsheet.setCell(“A1”, 10); // sets A1 to 10
spreadsheet.getValue("=A1+6"); // returns 16 (10+6)
spreadsheet.setCell(“B2”, 15); // sets B2 to 15
spreadsheet.getValue("=A1+B2"); // returns 25 (10+15)
spreadsheet.resetCell(“A1”); // resets A1 to 0
spreadsheet.getValue("=A1+B2"); // returns 15 (0+15)

Constraints:

• 1 <= rows <= 103
• 0 <= value <= 105
• The formula is always in the format "=X+Y", where X and Y are either valid cell references or non-negative integers with values less than or equal to 105.
• Each cell reference consists of a capital letter from 'A' to 'Z' followed by a row number between 1 and rows.
• At most 104 calls will be made in total to setCell, resetCell, and getValue.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Spreadsheet(object):

    def __init__(self, rows):
        """
        :type rows: int
        """
        self.tables = [[0] * rows for _ in range(26)]

    def setCell(self, cell, value):
        """
        :type cell: str
        :type value: int
        :rtype: None
        """
        col = ord(cell[0]) - ord('A')
        row = int(cell[1:]) - 1
        self.tables[col][row] = value

    def resetCell(self, cell):
        """
        :type cell: str
        :rtype: None
        """
        col = ord(cell[0]) - ord('A')
        row = int(cell[1:]) - 1
        self.tables[col][row] = 0


    def getValue(self, formula):
        """
        :type formula: str
        :rtype: int
        """
        x, y = formula[1:].split('+')
        x = int(x) if x.isdigit() else self.tables[ord(x[0])-ord('A')][int(x[1:])-1]
        y = int(y) if y.isdigit() else self.tables[ord(y[0])-ord('A')][int(y[1:])-1]
        return x + y


# Your Spreadsheet object will be instantiated and called as such:
# obj = Spreadsheet(rows)
# obj.setCell(cell,value)
# obj.resetCell(cell)
# param_3 = obj.getValue(formula)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Spreadsheet(object):

    def __init__(self, rows):
        """
        :type rows: int
        """
        self.tables = dict()
        

    def setCell(self, cell, value):
        """
        :type cell: str
        :type value: int
        :rtype: None
        """
        self.tables[cell] = value

    def resetCell(self, cell):
        """
        :type cell: str
        :rtype: None
        """
        if cell in self.tables:
            del self.tables[cell]

    def getValue(self, formula):
        """
        :type formula: str
        :rtype: int
        """
        x, y = formula[1:].split('+')
        x = int(x) if x.isdigit() else self.tables.get(x, 0)
        y = int(y) if y.isdigit() else self.tables.get(y, 0)
        return x + y


# Your Spreadsheet object will be instantiated and called as such:
# obj = Spreadsheet(rows)
# obj.setCell(cell,value)
# obj.resetCell(cell)
# param_3 = obj.getValue(formula)

3508. Implement Router 2025.09.21

Design a data structure that can efficiently manage data packets in a network router. Each data packet consists of the following attributes:

• source: A unique identifier for the machine that generated the packet.
• destination: A unique identifier for the target machine.
• timestamp: The time at which the packet arrived at the router.

Implement the Router class:

Router(int memoryLimit): Initializes the Router object with a fixed memory limit.

• memoryLimit is the maximum number of packets the router can store at any given time.
• If adding a new packet would exceed this limit, the oldest packet must be removed to free up space.

bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router.

• A packet is considered a duplicate if another packet with the same source, destination, and timestamp already exists in the router.
• Return true if the packet is successfully added (i.e., it is not a duplicate); otherwise return false.

int[] forwardPacket(): Forwards the next packet in FIFO (First In First Out) order.

• Remove the packet from storage.
• Return the packet as an array [source, destination, timestamp].
• If there are no packets to forward, return an empty array.

int getCount(int destination, int startTime, int endTime):

• Returns the number of packets currently stored in the router (i.e., not yet forwarded) that have the specified destination and have timestamps in the inclusive range [startTime, endTime].

Note that queries for addPacket will be made in increasing order of timestamp.

Example 1:

Input:
[“Router”, “addPacket”, “addPacket”, “addPacket”, “addPacket”, “addPacket”, “forwardPacket”, “addPacket”, “getCount”]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

Output:
[null, true, true, false, true, true, [2, 5, 90], true, 1]

Explanation

Router router = new Router(3); // Initialize Router with memoryLimit of 3.
router.addPacket(1, 4, 90); // Packet is added. Return True.
router.addPacket(2, 5, 90); // Packet is added. Return True.
router.addPacket(1, 4, 90); // This is a duplicate packet. Return False.
router.addPacket(3, 5, 95); // Packet is added. Return True
router.addPacket(4, 5, 105); // Packet is added, [1, 4, 90] is removed as number of packets exceeds memoryLimit. Return True.
router.forwardPacket(); // Return [2, 5, 90] and remove it from router.
router.addPacket(5, 2, 110); // Packet is added. Return True.
router.getCount(5, 100, 110); // The only packet with destination 5 and timestamp in the inclusive range [100, 110] is [4, 5, 105]. Return 1.

Example 2:

Input:
[“Router”, “addPacket”, “forwardPacket”, “forwardPacket”]
[[2], [7, 4, 90], [], []]

Output:
[null, true, [7, 4, 90], []]

Explanation

Router router = new Router(2); // Initialize Router with memoryLimit of 2.
router.addPacket(7, 4, 90); // Return True.
router.forwardPacket(); // Return [7, 4, 90].
router.forwardPacket(); // There are no packets left, return [].

Constraints:

• 2 <= memoryLimit <= 105
• 1 <= source, destination <= 2 * 105
• 1 <= timestamp <= 109
• 1 <= startTime <= endTime <= 109
• At most 105 calls will be made to addPacket, forwardPacket, and getCount methods altogether.
• queries for addPacket will be made in increasing order of timestamp.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

from collections import deque
class Router(object):

    def __init__(self, memoryLimit):
        """
        :type memoryLimit: int
        """
        self.size = memoryLimit
        self.packets = deque()

    def addPacket(self, source, destination, timestamp):
        """
        :type source: int
        :type destination: int
        :type timestamp: int
        :rtype: bool
        """
        if [source, destination, timestamp] in self.packets:
            return False
        else:
            self.packets.append([source, destination, timestamp])
            if len(self.packets) > self.size:
                self.packets.popleft()
            return True

    def forwardPacket(self):
        """
        :rtype: List[int]
        """
        if not self.packets:
            return []
        else:
            return self.packets.popleft()

    def getCount(self, destination, startTime, endTime):
        """
        :type destination: int
        :type startTime: int
        :type endTime: int
        :rtype: int
        """
        return len([i for i in self.packets if i[1]==destination and startTime <= i[2] <= endTime])


# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

from collections import deque, defaultdict
from bisect import bisect_left, bisect_right

class Router(object):

    def __init__(self, memoryLimit):
        """
        :type memoryLimit: int
        """
        self.size = memoryLimit
        self.packets = deque()
        self.packet_set = set()
        # For fast range queries: destination -> list of timestamps (sorted)
        self.dest_timestamps = defaultdict(list)

    def addPacket(self, source, destination, timestamp):
        """
        :type source: int
        :type destination: int
        :type timestamp: int
        :rtype: bool
        """
        packet_tuple = (source, destination, timestamp)
        
        if packet_tuple in self.packet_set:
            return False
        
        packet_list = [source, destination, timestamp]
        self.packets.append(packet_list)
        self.packet_set.add(packet_tuple)
        
        # Add to sorted timestamp list for this destination
        timestamps = self.dest_timestamps[destination]
        # Insert in sorted order using bisect
        pos = bisect_left(timestamps, timestamp)
        timestamps.insert(pos, timestamp)
        
        # Remove oldest packet if exceeding memory limit
        if len(self.packets) > self.size:
            removed_packet = self.packets.popleft()
            self.packet_set.remove(tuple(removed_packet))
            # Remove from timestamp tracking
            removed_dest = removed_packet[1]
            removed_time = removed_packet[2]
            self.dest_timestamps[removed_dest].remove(removed_time)
            if not self.dest_timestamps[removed_dest]:
                del self.dest_timestamps[removed_dest]
                
        return True

    def forwardPacket(self):
        """
        :rtype: List[int]
        """
        if not self.packets:
            return []
        
        forwarded_packet = self.packets.popleft()
        self.packet_set.remove(tuple(forwarded_packet))
        
        # Remove from timestamp tracking
        dest = forwarded_packet[1]
        timestamp = forwarded_packet[2]
        self.dest_timestamps[dest].remove(timestamp)
        if not self.dest_timestamps[dest]:
            del self.dest_timestamps[dest]
            
        return forwarded_packet

    def getCount(self, destination, startTime, endTime):
        """
        :type destination: int
        :type startTime: int
        :type endTime: int
        :rtype: int
        """
        if destination not in self.dest_timestamps:
            return 0
            
        timestamps = self.dest_timestamps[destination]
        if not timestamps:
            return 0
        
        # Use binary search to find range
        left_idx = bisect_left(timestamps, startTime)
        right_idx = bisect_right(timestamps, endTime)
        
        return right_idx - left_idx

3005. Count Elements With Maximum Frequency 2025.09.22

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    def maxFrequencyElements(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        freq_map = dict()
        for i in nums:
            if i in freq_map:
                freq_map[i] += 1
            else:
                freq_map[i] = 1
        
        freqs = [v for v in freq_map.values()]
        max_freq = max(freqs)
        return max_freq * freqs.count(max_freq)

165. Compare Version Numbers 2025.09.23

Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros.

To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0.

Return the following:

• If version1 < version2, return -1.
• If version1 > version2, return 1.
• Otherwise, return 0.

Example 1:

Input: version1 = “1.2”, version2 = “1.10”

Output: -1

Explanation:

version1’s second revision is “2” and version2’s second revision is “10”: 2 < 10, so version1 < version2.

Example 2:

Input: version1 = “1.01”, version2 = “1.001”

Output: 0

Explanation:

Ignoring leading zeroes, both “01” and “001” represent the same integer “1”.

Example 3:

Input: version1 = “1.0”, version2 = “1.0.0.0”

Output: 0

Explanation:

version1 has less revisions, which means every missing revision are treated as “0”.

Constraints:

• 1 <= version1.length, version2.length <= 500
• version1 and version2 only contain digits and '.'.
• version1 and version2 are valid version numbers.
• All the given revisions in version1 and version2 can be stored in a 32-bit integer.

Solution

Filling the trailing zeros and using tuple comparison

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        v1 = version1.split('.')
        v2 = version2.split('.')
        v1 = [int(i) for i in v1]
        v2 = [int(i) for i in v2]
        m,n = len(v1), len(v2)
        if m > n:
            for i in range(m-n):
                v2.append(0)
        else:
            for i in range(n-m):
                v1.append(0)
        
        if tuple(v1) > tuple(v2):
            return 1
        elif tuple(v1) < tuple(v2):
            return -1
        else:
            return 0

166. Fraction to Recurring Decimal 2025.09.24

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 104 for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2 Output: “0.5”

Example 2:

Input: numerator = 2, denominator = 1 Output: “2”

Example 3:

Input: numerator = 4, denominator = 333 Output: “0.(012)”

Constraints:

• -231 <= numerator, denominator <= 231 - 1
• denominator != 0

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type digiterator: int
        :type denominator: int
        :rtype: str
        """
        sign = '-' if numerator * denominator < 0 else ''
        denominator = abs(denominator)
        numerator = abs(numerator)

        integer = numerator // denominator
        res = numerator % denominator

        if res == 0:
            return sign + str(integer)

        rems = list()
        digits = list()
        while res != 0 and res not in rems:
            rems.append(res)
            res *= 10
            digit, res = res // denominator, res % denominator
            digits.append(digit)

        digits = [str(_) for _ in digits]
        if res == 0:
            decimal = ''.join(digits)
            return sign + str(integer)+'.'+decimal
        else:
            idx = rems.index(res)
            decimal = ''.join(digits[:idx]) + '(' + ''.join(digits[idx:]) + ')'
            return sign + str(integer)+'.'+decimal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if numerator == 0:
            return "0"

        # Handle sign
        sign = '-' if numerator * denominator < 0 else ''
        numerator, denominator = abs(numerator), abs(denominator)

        # Integer part
        integer = numerator // denominator
        res = numerator % denominator

        if res == 0:
            return sign + str(integer)

        # Dictionary for remainder -> position in decimal
        rem_map = {}
        digits = []

        while res != 0:
            if res in rem_map:
                idx = rem_map[res]
                decimal = ''.join(digits[:idx]) + '(' + ''.join(digits[idx:]) + ')'
                return sign + str(integer) + '.' + decimal

            rem_map[res] = len(digits)  # store index for cycle detection
            res *= 10
            digit, res = divmod(res, denominator)
            digits.append(str(digit))

        # No repeating cycle
        decimal = ''.join(digits)
        return sign + str(integer) + '.' + decimal

120. Triangle 2025.09.25

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:

   2  
  3 4  
 6 5 7  
4 1 8 3  

The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Solution

Dynamic Planning

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)

        dp = [[0]*_ for _ in range(1,n+1)]
        dp[0][0] = triangle[0][0]
        for i in range(1,n):
            dp[i][0] = dp[i-1][0] + triangle[i][0]
        for i in range(1, n):
            for j in range(1,i+1):
                if i == j:
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]
        return min(dp[-1])

611. Valid Triangle Number 2025.09.26

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Solution

2 pointers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        n = len(nums)
        count = 0

        for right in range(2, n):
            left,mid = 0, right - 1
            while left < mid:
                if nums[left] + nums[mid] > nums[right]:
                    count += mid - left
                    mid -= 1
                else:
                    left += 1
        return count

812. Largest Triangle Area 2025.09.27

Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000
Explanation: The five points are shown in the above figure. The red triangle is the largest.

Example 2:

Input: points = [[1,0],[0,0],[0,1]]
Output: 0.50000

Constraints:

• 3 <= points.length <= 50
• -50 <= xi, yi <= 50
• All the given points are unique.

Solution

brutal force loop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution(object):
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        def tri_area(pt1, pt2, pt3):
            x1,y1 = pt1
            x2,y2 = pt2
            x3,y3 = pt3

            return 0.5*abs(x2*y3-x3*y2-x1*y3+x3*y1+x1*y2-x2*y1)
        n = len(points)

        max_area = 0
        for i in range(n-2):
            for j in range(i, n-1):
                for k in range(j, n):
                    max_area = max(tri_area(points[i],points[j],points[k]), max_area)
        return max_area

976. Largest Perimeter Triangle 2025.09.28

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1,10]
Output: 0
Explanation: You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints:

• 3 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^6

Solution

Greedy algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution(object):
    def largestPerimeter(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort(reverse=True)
        n = len(nums)
        for i in range(n-2):
            if nums[i+1] + nums[i+2] > nums[i]:
                return nums[i] + nums[i+1] + nums[i+2]
        
        return 0

2221. Find Triangular Sum of an Array 2025.09.30

You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the value of the only element present in nums after the following process terminates:

1. Let nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
2. For each index i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
3. Replace the array nums with newNums.
4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Example 1:

Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2:

Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

Recurrsion

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution(object):
    def triangularSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def helper(nums):
            if len(nums) == 1:
                return nums[0]
            
            return helper([(nums[i]+nums[i+1]) % 10 for i in range(len(nums)-1)])
        
        return helper(nums)

1518. Water Bottles 2025.10.01

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Constraints:

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

Solution

Follow the instruction

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution(object):
    def numWaterBottles(self, numBottles, numExchange):
        """
        :type numBottles: int
        :type numExchange: int
        :rtype: int
        """
        count = numBottles
        currBottle = numBottles
        while currBottle >= numExchange:
            count += currBottle // numExchange
            currBottle = currBottle // numExchange + currBottle % numExchange
        return count

3100. Water Bottles II 2025.10.02

You are given two integers numBottles and numExchange.

numBottles represents the number of full water bottles that you initially have. In one operation, you can perform one of the following operations:

• Drink any number of full water bottles turning them into empty bottles.
• Exchange numExchange empty bottles with one full water bottle. Then, increase numExchange by one.

Note that you cannot exchange multiple batches of empty bottles for the same value of numExchange. For example, if numBottles == 3 and numExchange == 1, you cannot exchange 3 empty water bottles for 3 full bottles.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 13, numExchange = 6
Output: 15
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Example 2:

Input: numBottles = 10, numExchange = 3
Output: 13
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Constraints:

• 1 <= numBottles <= 100
• 1 <= numExchange <= 100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    def maxBottlesDrunk(self, numBottles, numExchange):
        """
        :type numBottles: int
        :type numExchange: int
        :rtype: int
        """
        currBottles = count = numBottles
        currExchange = numExchange
        while currBottles >= currExchange:
            currBottles =  currBottles - currExchange + 1
            currExchange += 1
            count += 1
        return count

417. Pacific Atlantic Water Flow 2025.10.05

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
  [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
  [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
  [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
  [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
  [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
  [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

Solution

DFS or BFS from different sides and find intersections

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

from collections import deque
from typing import List


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        n = len(heights)
        m = len(heights[0])

        def neight_pts(i, j):
            directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            return [
                (i + dx, j + dy)
                for dx, dy in directions
                if 0 <= i + dx < n
                and 0 <= j + dy < m
                and heights[i + dx][j + dy] >= heights[i][j]
            ]

        pacific_q = deque([(i, 0) for i in range(n)] + [(0, j) for j in range(m)])
        atlantic_q = deque(
            [(i, m - 1) for i in range(n)] + [(n - 1, j) for j in range(m)]
        )
        p = set(pacific_q)
        a = set(atlantic_q)
        while pacific_q:
            i = pacific_q.popleft()
            for j in neight_pts(*i):
                if j not in p:
                    p.add(j)
                    pacific_q.append(j)

        while atlantic_q:
            i = atlantic_q.popleft()
            for j in neight_pts(*i):
                if j not in a:
                    a.add(j)
                    atlantic_q.append(j)

        print(p)
        print(a)
        return [[i, j] for i, j in p & a]