DEV Community: Di Kan

Leetcode Reflection 3.23-3.29

Di Kan — Sun, 29 Mar 2026 03:44:46 +0000

Hi this is Di. It has been a while since last time I post the blog. I hada a time indulging in the Elden Ring: Nightreign. But it did no help to my career and knowledge. So i guess im back on that.

452. Minimum number of arrows to burst balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

This problem is quite similar to the interval problems before. But this time we should find the intersection of two overlapping interval. My first thought is to reuse the code before and fix max to min. Since it only require the number of the arrows, though there is a little inaccuracy in it, but it still work.

The optimized version of it is as follows:

def findMinArrowShots(self, points: list[list[int]]) -> int:
        if not points:
            return 0

        # Sort balloons by their end coordinates
        points.sort(key=lambda x: x[1])

        # Initialize the first arrow at the end of the first balloon
        arrows = 1
        current_end = points[0][1]

        for i in range(1, len(points)):
            # If the current balloon starts after the last arrow's range
            if points[i][0] > current_end:
                arrows += 1
                # Update the position of the arrow to the end of the current balloon
                current_end = points[i][1]

        return arrows

After sorting the intervals by end point in ascending order, if the first balloon got be bursted, the best position is at the end because if the second balloon is overlapped with it, one arrow can burst two. This method requires less storage memory.

71. Simplify Path

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.
The rules of a Unix-style file system are as follows:
A single period '.' represents the current directory.
A double period '..' represents the previous/parent directory.
Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.
Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.
The simplified canonical path should follow these rules:
The path must start with a single slash '/'.
Directories within the path must be separated by exactly one slash '/'.
The path must not end with a slash '/', unless it is the root directory.
The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.
Return the simplified canonical path.

To be honest, at first glance i have totally no idea what's going on to use a stack to solve it until i found the secret of split().

The funtion split("/") will return all the elements between "/". Even if ///, it will return ["","","",""],including head and tail.

So when we encounter "..", if the stack is not empty, we just pop it out because ".." represent the last directory.

At last we "/".join the stack. The join fucntion will not add leading and trailing "/".

 def simplifyPath(self, path: str) -> str:
        # Split the path by '/' and filter out empty strings and '.'
        # Example: "/a/./b/../../c/" -> ["a", ".", "b", "..", "..", "c"]
        parts = path.split("/")
        stack = []

        for part in parts:
            if part == "..":
                # Go up one level if the stack is not empty
                if stack:
                    stack.pop()
            elif part == "." or not part:
                # Ignore current directory markers and consecutive slashes
                continue
            else:
                # Valid directory name, push to stack
                stack.append(part)

        # Join the stack elements with '/' and ensure it starts with '/'
        return "/" + "/".join(stack)

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

At first glance, i feel like the min heap problem. Yet it's not the same. The good practice is mantain two stacks. One serves as the normal stack while the other records the min element.

We treat the first element as the first min and when new element comes which is less or equal than it, we also push it to the min list, and change the min to it.

class MinStack:
    def __init__(self):
        # Main stack to store all elements
        self.data_stack = []
        # Auxiliary stack to store minimum values
        self.min_stack = []

    def push(self, val: int) -> None:
        self.data_stack.append(val)
        # If min_stack is empty, or the new value is <= the current minimum
        # We must use <= to handle duplicate minimum values correctly
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        # If the element being popped is the current minimum, pop it from min_stack too
        if self.data_stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        # Standard stack top operation
        return self.data_stack[-1]

    def getMin(self) -> int:
        # The top of min_stack is always the minimum of data_stack
        return self.min_stack[-1]

141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Still hit me clueless at first. Then I get the idea of fast-slow pointer. The fast pointer go 2 steps while the slow pointer go 1 step. If a linkedlist has no cycle, the fast pointer shall be bound to reach the end first. In other hand, if a linkedlist has a cycle, the fast one will enter the cycle and finally reach the slow one. But before we jump the fast pointer, we should make sure the fast.next and fast themselves exist, or error will pop out.

def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head

        # Move fast and slow pointers
        while fast and fast.next:
            slow = slow.next          # Move 1 step
            fast = fast.next.next     # Move 2 steps

            # If they meet, there is a cycle
            if slow == fast:
                return True

        # If fast reaches the end, no cycle exists
        return False

Leetcode Reflection 3.16-3.22

Di Kan — Tue, 24 Mar 2026 05:44:29 +0000

Hi this is Di again. I realize it's too clumsy to post for every leetcode problem I solved. Therefore I decided to accumalate one weeks' reflection together and post them once.

202. Happy Number

If we add on all the square of a number's every digit, it end up with result 1, we call this number is a happy number.

It's easy to end the loop by detecting the emerge of 1. But how can we know when to end the endless loop without knowing whether 1 will appear?

Here is the maths prove behind it:

For one digit numbers, the max is 9, its square sum is 81, far bigger than 9.
For two digit numbers, the max is 99, its square sum is 81+81=162, slightly bigger than 99.
For three digit numbers, the max is 999, its square sum is 81x3=243, far less than 999
For four digit numbers, the max is 9999, its square sum is 81x4=324, far less than 9999

No matter how large the number is, after first calculation, it will collapse into range 1-999. Then turn into 1-243 in next iteration, then converged into this range forever. In endless loop, the 243 numbers will eventually appeared once. If a number come up twice, the number is sure to be "unhappy".

According to this convincing theory, our strategy is to loop until we find 1 or some number appears twice. Within the loop, we use a loop to calculate the square sum.

 def isHappy(self, n: int) -> bool:
        myset = set()
        while n != 1 and n not in myset:
            myset.add(n)
            res = 0

            while n != 0:
                thedigit = n % 10
                res += pow(thedigit, 2)
                n = n // 10
            n = res

        return n == 1

It's not that easy to come up with the idea of set() to document duplicate without knowing the convergence theory behind. Harder than Easy tier.

128.Longest consecutive sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

To find it in O(n) time, we are going to examine whether each element is the starter number in sequence. For number n, if n-1 is in the nums, skip it, because it's not the beginner. Else, find the following elements until not satisfied.

  def longestConsecutive(self, nums: List[int]) -> int:
        # Convert list to set to satisfy the Container interface with O(1) lookups
        num_set = set(nums)
        longest_streak = 0

        for num in num_set:
            # Check if 'num' is the start of a sequence
            # If (num - 1) exists, 'num' is NOT a start, so we skip it
            if (num - 1) not in num_set:
                current_num = num
                current_streak = 1

                # Keep counting the length of this consecutive sequence
                while (current_num + 1) in num_set:
                    current_num += 1
                    current_streak += 1

                # Update the maximum streak found so far
                longest_streak = max(longest_streak, current_streak)

        return longest_streak

The main idea is to find the beginning element and calculate the length of the sequence.

But why set instead of list?

The underlying implementation of set() is hashmap, allowing O(1) time search.

56.Merge intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

It's not hard to think of greedy method. But a segent of simple and elegant code snippet is precious.

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
      if not intervals:
            return []

        # 2. Sort intervals by start time (O(n log n))
        # Note: list.sort() is in-place and efficient in Python
        intervals.sort(key=lambda x: x[0])

        merged = []

        for curr_start, curr_end in intervals:
            # DRY: If merged is empty or no overlap, append the interval
            # The 'if not merged' handles the initialization of the result list
            if not merged or merged[-1][1] < curr_start:
                merged.append([curr_start, curr_end])
            else:
                # Overlap: Update the end time of the last merged interval
                # Use max() to ensure we cover the largest possible range
                merged[-1][1] = max(merged[-1][1], curr_end)

        return merged

Lamda expression
Notice intervals.sort(key=lambda x: x[0]).
this lamda expression allows you to sort the array by any key. xhere is the every element in the list. If we want to have priority, use tuple to assign.
Sequence Unpacking
"We can unpack the intervals directly in the for-loop header to improve readability."
for curr_start, curr_end in intervals:The members in the list are lists with 2 elements in it. So this unpacking is quite smart and time-saving, and readability-strengthening.
Interval situations.
When two intervals are overlapped.

The first former one completely includes the latter one.
Two intervals have partial intersection.
These can be all tackled by merged[-1][1] = max(merged[-1][1], curr_end)
Cuz we just want the farthest end of the interval.

57.Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

It's quite similar to leetcode 56 except we have to insert the new interval into the intervals and do the algorithms in 56 again.

 def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            intervals.append(newInterval)
            return intervals

        if not newInterval:
            return intervals

        res = []
        inserted = False
        for i in range(len(intervals)):
            start,end = intervals[i]
            if start >= newInterval[0]:
                intervals.insert(i,newInterval)
                inserted = True
                break

        if inserted == False:
            intervals.append(newInterval)


        for start,end in intervals:
            if not res or res[-1][1] < start:
                res.append([start,end])
            else:
                res[-1][1] = max(res[-1][1], end)
        return res

Use a flag inserted to trace the new interval. If it's gonna be the last one in intervals, the flag would still be False, then deal with it at last.

What I learned in leetcode 49 Group Anagrams

Di Kan — Mon, 16 Mar 2026 09:22:00 +0000

Hi this is Di. I am glad to finally begin my blogger life in such an influential platform. I used to write something in my own tiny bare-shell website. But I realized the key to the progress is the spread and clash of the ideas. So I come here. I think the way to a better software engineer, even a better person, learning-criticizing-reflecting-optimizing loop is necessary for my own career and mind. The blog provide me an ideal place to be criticizing and reflecting, and that's the way I always decide to do it. Maybe it's a kind of imitations from the what gurus did.

After leaving the school, i feel like a sense of way different views. The courses to all the corner of the society is open to me now. I feel lost and confused in front of this mist like the tarnished before the mist door. The unknown and big challenge are hiding behind it and unfortunately I can't be brought back by the golden tree in ELDEN RING. Therefore, it's time to sharpen my sword and fight for myself. In the end, it's my own life.

As you can tell prolly, my language expression is not authetic and natural enough. But giving up the practice means ignoring the course to better.

Time to grind.

49.Group Anagrams.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.
Given a string list, our job is to group all the anagrams.

At first, my idea is to use Counter as a key to store all the words with the same Counter, which can count the frequency of each letter appeared. But the dict can't use a variable as a key.

Then I turned to Gemini for help, which is the best solution to acquire the optimal after my own thinking.

 def groupAnagrams(self, strs):
        # Use a dictionary where the key is the character count tuple
        # and the value is a list of strings belonging to that anagram group
        ans = defaultdict(list)

        for s in strs:
            # Initialize a count array for 26 lowercase English letters
            count = [0] * 26
            for char in s:
                # Calculate the index (0 for 'a', 1 for 'b', etc.)
                count[ord(char) - ord('a')] += 1

            # Convert list to tuple to make it hashable
            ans[tuple(count)].append(s)

        return list(ans.values())

The main idea is to use a 26-length tuple to store the words because the tuple is invariant.

1. defaultdict

ans = defaultdict(list)

defaultdict avoids the pop-out error when the key is not in the dict. We can assign a default data type for those unvisited.

2. ord('a')
ord() stands for the abbr for ordinal. It will return the ASCII number corresponding to a character. ord('a') = 97，ord('A') = 65.

By calculating the offset from the 97, we can tell where to count the letter in tuple.

3. list(ans.values()
Maybe you are also curious about why not just return the ans.values instead of listing it?

Actually two different types implement different interfaces. dict_values implements the ValuesView interface, while list implements MutableSequence interface.

"In the Python ecosystem, base interfaces like Sized or Iterable are essentially formal wrappers around a single Protocol. They define a specific capability (e.g., being measurable or traversable). As we move towards more complex structures like Sequence, we see a Composition of Protocols. Understanding this allows us to see data structures not as black boxes, but as a collection of implemented capabilities."

To satisfy the need to judge your solution, official requried the result to be gettable. But ValuesView does not implement that protocal.