Data Structures

• 1: Arrays & Strings
• 1.1: 1. Two Sum
• 2: Trees
• 2.1: 199. Binary Tree Right Side View
• 3: Graphs
• 4: Linked Lists

1 - Arrays & Strings

1.1 - 1. Two Sum

Problem Description

LeetCode Problem Link

Given an array of integers nums and an integer target, return indices of the two numbers in nums such that they add up to target.

Constraints:

• 2 ≤ nums.length ≤ 104
• -109 ≤ nums[i] ≤ 109
• -109 ≤ target ≤ 109
• Only one valid answer exists

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]

Intuition and Approach

Intuition

For each number in the array, we need its complement (target - number) to form the target sum. Instead of searching for this complement repeatedly, we can use a hash map for O(1) lookups.

Approach

1. Create a hash map to store number-to-index mappings
2. Iterate through the array once:
   • Calculate the complement (target - current number)
   • Check if complement exists in hash map
   • If found, return current index and complement’s index
   • If not found, store current number and its index

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    
    for i, num := range nums {
        complement := target - num
        if j, exists := seen[complement]; exists {
            return []int{j, i}
        }
        seen[num] = i
    }
    return nil
}

Time and Space Complexity

Time Complexity: O(n)

• Single pass through the array
• Hash map operations (insertion and lookup) are O(1)

Space Complexity: O(n)

• Hash map stores at most n elements
• Additional space grows linearly with input size

2 - Trees

2.1 - 199. Binary Tree Right Side View

Problem Description

LeetCode Problem Link

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤ Node.val ≤ 100

Example:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The nodes visible from the right side are 1, 3, and 4.

Intuition and Approach

Intuition

When viewing a binary tree from the right side, we want to see the rightmost node at each level. Using a queue for level-order traversal (BFS), we can capture the last node at each level to build our right-side view.

Approach

1. Use a queue to perform level-order traversal
2. For each level:
   • Get the current level size
   • Process all nodes at this level
   • Add the last node’s value to our result
3. Return the collected right-side values

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    result := []int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            // If it's the last node in current level, add to result
            if i == levelSize-1 {
                result = append(result, node.Val)
            }
            
            // Add children to queue
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return result
}

Time and Space Complexity

Time Complexity: O(n)

• Visit each node exactly once
• Queue operations are O(1)

Space Complexity: O(w)

• w is the maximum width of the tree
• In worst case (perfect binary tree), the last level has n/2 nodes
• Queue stores at most one level at a time

3 - Graphs

4 - Linked Lists