---

Solved Problems 📝

241221

• 15. 3Sum - my solution
• 105. Construct Binary Tree from Preorder and Inorder Traversal - my solution

---

Key Learnings 🤔

how to skip duplicates in two-pointer solutions using three indices?

to avoid processing redundant duplicate values in problems like 3Sum

👉 skip duplicates, using conditions and multiple pointers.(indices)
👉 ensures that you don't include duplicate triplets in the result, such as [[1, 0, -1], [1, 0, -1]]

15. 3Sum: https://leetcode.com/problems/3sum/description/

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # TC: O(n log n), SC: O(1)
        result = [] # result are part of the output => do not count toward auxiliary (extra) space.

        for i in range(len(nums)): # TC: O(n^2)
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            j = i + 1
            k = len(nums) - 1
            while j < k:
                currSum = nums[i] + nums[j] + nums[k]

                if currSum < 0:
                    j += 1
                elif currSum > 0:
                    k -= 1
                else:
                    result.append([nums[i], nums[j], nums[k]]) 

                    while j < k and nums[j] == nums[j + 1]:
                        j += 1
                    while j < k and nums[k] == nums[k - 1]: 
                        k -= 1

                    j += 1
                    k -= 1

        return result

• Skip duplicates for the main loop (i):

if i > 0 and nums[i] == nums[i - 1]:
    continue

• Skip duplicates for the second pointer (j):

while j < k and nums[j] == nums[j + 1]:
    j += 1

• Skip duplicates for the third pointer (k):

while j < k and nums[k] == nums[k - 1]:
    k -= 1

why do results not count toward auxiliary (extra) space?

when evaluating space complexity, result is considered as part of the output rather than extra space.

auxiliary space vs. total space

• Auxiliary space(보조 공간) refers to the additional memory used by the algorithm, excluding the input and output. This typically includes variables, temporary data structures, and extra memory required during execution.

• Total space(전체 공간) includes both the auxiliary space and the space used by the input and output.

👉 in a problem 3Sum, the result array holds the triplets, that considered as part of the output. so it doesn’t contribute to auxiliary space. It is simply the memory space used to store the answer, which is part of the final result.

preorder & inorder traversals in bst

105. Construct Binary Tree from Preorder and Inorder Traversal: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

preorder traversal (전위 순회)

in preorder traversal, the root node is processed before its left and right subtrees.

The order of processing is:

• Process the root node.
• Traverse the left subtree.
• Traverse the right subtree.

inorder traversal (중위 순회)

in inorder traversal, the left subtree is processed first, followed by the root node, and then the right subtree.

in a bst, inorder traversal produces the nodes in sorted order.

preorder traversal: Root → Left → Right
inorder traversal: Left → Root → Right

why both preorder and inorder are necessary for building tree's structure?

• preorder: identify the root of the current subtree.
• inorder: allows to split the tree into left and right subtrees

enumerate() in python

enumerate() is a built-in function that adds a counter to an iterable and returns it as an enumerate object. It’s often used in loops when you need both the index and the value of items in a list.

for index, value in enumerate(inorder):
    print(index, value)

iterators in python

iter(preorder)

iterator is an object that can be iterated (looped) upon, returns one element at a time when you use the next() function.
using iterators can help with efficient memory usage when processing large data or streams.

👉 to convert an iterable into an iterator in python => use iter().

preorder = [3, 9, 20, 15, 7]
preorder_iter = iter(preorder)

print(next(preorder_iter))  # Output: 3
print(next(preorder_iter))  # Output: 9