July 5, 2025 - Leetcode Drill¶

🎯 Daily Goals¶

Review Anki Deck
Lumosity Training
Leetcode problem

📝 What I Learned¶

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

Topics: HashTable, Priority Queue, Array¶

📝 Thinking Process:¶

The brute force solution is easy to come up with. Where we iterate through all possible combination of i, j, k and check if the x[i], x[j], x[k] are distinct if so then we update the maximum sum. If not we continue. This approach would take O(n³) time. This question would be very easy if all x values are distinct since we just need to check the top 3 largest y values and then take the sum and return it. So to make it distinct, we can actually iterate through all x values and store the highest y value for the corresponding x value. Then we iterate through all the selected y values and pick the top three. We can do this by pushing them onto a max heap and pick the top three elements.

👨‍💻 Big O analysis:¶

Assume we have n elements in the x array, and they have k distinct values. Time Complexity: O(n + klogk) Space Complexity: O(k) Reasoning: We iterate through the array x and created a hashmap with k distinct value. Then we pushed these k distinct values onto a priority queue and popped three of them.

🛫 Implementation takeaways:¶

To easily iterate through the x and y pairs, don't iterate through the same index. Use zip() instead.
Find top3 largest elements using heaqp.nlargest(3, arr)

1152. Analyze User Website Visit Pattern

Topics: Array, Sorting, String¶

📝 Thinking Process:¶

Given the constraints from the prompt we can see that a naive solution would be enough. What we need to do is to zip the timestamp, username and website together sort them by timestamp and group them by user. And then get the unique patterns from each user. And count the appearance for each pattern and select the one with the highest one.

👨‍💻 Big O analysis:¶

Assume user visited approximately n websites and there are k distinct usernames.

Time Complexity: O(knlog(kn) + O(kn³))
Space Complexity: O(kn) + O(kn³) =

Reason: we first sort the zipped tupples and then get the combination or pattern of the websites of each user. Then we iterate through all these combinations and create a counter for each pattern. Then we pick the top one.

🛫 Implementation takeaways:¶

combinations function would preserve the original order.
use zip and sort to sort multiple parallel arrays by only one of them.
The update function

📃 A Reference Solution:¶

    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:

        users = defaultdict(list)

        for user, time, site in sorted(zip(username, timestamp, website), key = lambda x: (x[0],x[1])): 
            users[user].append(site)

        patterns = Counter()

        for user, sites in users.items():
            patterns.update(Counter(set(combinations(sites, 3))))

        return max(sorted(patterns), key=patterns.get)

Thanks shrey for the concise answer

🚀 Concepts that Requires Further Study:¶

itertool library