Category: Uncategorized

Climbing Stairs is probably the first problem that forces you to actually think about optimization. For many people, it’s also their first real introduction to Dynamic Programming (DP). At its core, DP is just the idea of remembering work you’ve already done so you don’t repeat it. It’s a great problem to get your feet wet in that domain.

The Problem

The problem asks that you climb a staircase by either taking one step or two steps. How many distinct ways can we climb to the top given a stair case of size n?

For example, if we are given a staircase of size 2 then there are only two ways to climb to the top.

• 1 step + 1 step 

• 2 steps

Similarly if n was 3 then we would have 3 ways to climb the staircase:

• 1 step + 1 step + 1 step

• 2 steps + 1 step

• 1 step + 2 steps

Solution

Lets try to solve this problem by brute force by hand first. If we try to write out solutions by hand we will start to notice an interesting pattern:

If n was 4 we would have 5 ways to climb the stairs

• 1 step + 1 step + 1 step + 1 step

• 2 steps + 1 step + 1 step

• 1 step + 2 steps + 1 step

• 1 step + 1 step + 2 steps

• 2 steps + 2 steps

Similarly if we do n = 5 we would get 8 (I’ll skip writing out all the possible combinations). More importantly we would notice an interesting pattern emerge:

If n = 1 then we get 1

If n = 2 then we get 2

If n = 3 then we get 3

If n = 4 then we get 5

If n = 5 then we get 8

…. and so on

Do you see the pattern? Each number is the sum of the two before it. That’s just the Fibonacci sequence. This whole problem reduces to computing Fibonacci numbers.

Naive Solution

Anyways, the naive solution is to code the sequence using recursion:

public static int climbStairs(int n) {
  if (n == 1) {
      return 1;
  }


  if (n == 2) {
      return 2;
  }


  return climbStairs(n - 1) + climbStairs(n - 2);
}

public static int climbStairs(int n) {
  if (n == 1) {
      return 1;
  }


  if (n == 2) {
      return 2;
  }


  return climbStairs(n - 1) + climbStairs(n - 2);
}

We set up a base case for the first two numbers in the sequence and otherwise we would work our way backwards to find the solution we need. This would give us the correct solution but this would not be accepted by LeetCode. It would get rejected not because it’s incorrect but because it’s too slow. As N gets large the function becomes slower dramatically. 

Naive Solution Time and Space Complexity

How slow exactly? Let’s find out. If we graph out an execution of this method for n = 5 the recursions make a pretty binary tree for us:

climbStairs(5)

├── climbStairs(4)

│   ├── climbStairs(3)

│   │   ├── climbStairs(2) → 2

│   │   └── climbStairs(1) → 1

│   └── climbStairs(2) → 2

└── climbStairs(3)

    ├── climbStairs(2) → 2

    └── climbStairs(1) → 1

If we count each node in this tree as an execution of our method then this means the cost to run this solution will grow exponentially as n gets bigger. In general that means that our algorithm has a time complexity of O(2^N). Since the computer walks through this tree depth first (it goes from the root to one leaf before it visits another leaf) the space complexity is O(N) since the path from the root to the leaf of the tree would be at most N. As a result at most N calls of the recursive function would be on the call stack (and thus memory) at any given time.

Memoized Solution

We can make this program much faster by taking advantage of a pattern we see in the tree above. We often repeat the same work throughout the tree. What if instead of redoing that we remembered what we had done last time and used that? The act of remembering previous calculations is the core technique of dynamic programming. We can store the results of previous calculations in a variable called memo and do the same calculations as we go.

public static int climbStairs(int n) {
   List<Integer> memo = new ArrayList<>();
   // take care of our base cases of when n = 0, 1, or 2
   memo.add(0);
   memo.add(1);
   memo.add(2);


   while(n >= memo.size()) {
       int currentSize = memo.size();
       memo.add(memo.get(currentSize - 1) + memo.get(currentSize - 2));
   }


   return memo.get(n);
}

public static int climbStairs(int n) {
   List<Integer> memo = new ArrayList<>();
   // take care of our base cases of when n = 0, 1, or 2
   memo.add(0);
   memo.add(1);
   memo.add(2);


   while(n >= memo.size()) {
       int currentSize = memo.size();
       memo.add(memo.get(currentSize - 1) + memo.get(currentSize - 2));
   }


   return memo.get(n);
}

Like before we record some values for the base cases but instead of calling the function over and over we just look at the last two values we calculated to determine the next one. Since we only ever do calculation for a new number once this solution is much faster.

Memoized Time and Space Complexity

How much faster? Well if we are only ever calculating new numbers once then at most the number of times we would calculate numbers in the sequence is O(n). Similarly, since our code needs to store an array of size n our space complexity remains O(n).

Optimal Space Solution

We can do even better than this in terms of space though. Since we only really need to remember the last two values it doesn’t make sense to keep all the old values we calculated in an array. Instead we could just keep track of the last two values to be more efficient.

public int climbStairs(int n) {
    int current = 2;
    int before = 1;

    if (n == 1) {
        return before;
    }

    if (n == 2) {
        return current;
    }

    int temp;
    for(int i = 3; i <= n; i++) {
        temp = before;
        before = current;
        current = temp + before;
    }

    return current;
}

public int climbStairs(int n) {
    int current = 2;
    int before = 1;

    if (n == 1) {
        return before;
    }

    if (n == 2) {
        return current;
    }

    int temp;
    for(int i = 3; i <= n; i++) {
        temp = before;
        before = current;
        current = temp + before;
    }

    return current;
}

This lets us keep our O(n) speed but actually reduces our space usage to just O(1).

Key Takeaways

The solution starts off as a straightforward variation of generating the fibonacci sequence but forces the user to approach the same problem with a different mindset as they run against performance constraints. In many ways this program is a great introduction to dynamic programming and evolving past beginner programming challenges to more advanced problems. 

Merging two sorted lists is both a programming technique and a LeetCode problem! It’s a part of the blind 75 and is a foundational problem to understand since it sets us up for understanding important algorithms like merge-sort down the line.

If you would prefer a video version of this explanation you can check it out at my youtube channel!

The Problem

According to the LeetCode website:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

Input: list1 = [], list2 = [0]

Output: [0]

Solution

The algorithm itself is straightforward.Since we know that the provided linked lists are already sorted we can go through the elements in each list sequentially, compare them to each other, and progressively build the output as we read both. More specifically the algorithm would look like this:

1. While we have data to read in both list1 and list2:
   1. Compare the current value we are on at list1 to the current value we are on at list2
      1. If the current value of list1 is less than that of list2
         1.  add the current value list1 to the output list
         2.  Mark the current value of list1 as read and get ready to read the next.
      2. Otherwise
         1.  add the current value of list2 to the output list
         2.  Mark the current value of list2 as read and get ready to read the next.
2. If we still have data in list1 but not in list2 then append all the remaining data in list1 to the output.
3. otherwise append all the remaining data in list2 to the output since we know that list2 is not empty.

The logic seems straightforward but there are actually two different implementations for it: an iterative and a recursive approach. We will walk through both in this post. Let’s start with the iterative implementation since it is easier to understand.

Iterative implementation

The iterative approach maps to our pseudocode above quite nicely.

public ListNode mergeTwoListsIterative(ListNode list1, ListNode list2) {
   // we initialize the output with a dummy node to make adding to it easier
   ListNode output = new ListNode();
   ListNode outputPointer = output;


   // go through the nodes of each list and compare them to each other
   while(list1 != null && list2 != null) {
       if (list1.val < list2.val) {
           outputPointer.next = list1;
           list1 = list1.next;
       } else {
           outputPointer.next = list2;
           list2 = list2.next;
       }
       outputPointer = outputPointer.next;
   }


   // flush the remaining data of whichever list is not empty to the output
   outputPointer.next = (list1 != null) ? list1 : list2;


   // send output but without the dummy node
   return output.next;
}

public ListNode mergeTwoListsIterative(ListNode list1, ListNode list2) {
   // we initialize the output with a dummy node to make adding to it easier
   ListNode output = new ListNode();
   ListNode outputPointer = output;


   // go through the nodes of each list and compare them to each other
   while(list1 != null && list2 != null) {
       if (list1.val < list2.val) {
           outputPointer.next = list1;
           list1 = list1.next;
       } else {
           outputPointer.next = list2;
           list2 = list2.next;
       }
       outputPointer = outputPointer.next;
   }


   // flush the remaining data of whichever list is not empty to the output
   outputPointer.next = (list1 != null) ? list1 : list2;


   // send output but without the dummy node
   return output.next;
}

Recursive implementation

The recursive implementation is the same idea but the main paradigm shift is that instead of tracking where we are using pointers we rely on the function’s call stack to keep track of the ordering for us. This results in less code but it can be harder to read if you are not comfortable with the concept of recursion. 

If you look at our code below it is very much like our pseudocode but in reverse. We address our base cases if either of the lists are empty and otherwise compare and sort the nodes one by one.

public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
   if (list1 == null) {
       return list2;
   }


   if (list2 == null) {
       return list1;
   }


   if (list1.val < list2.val) {
       list1.next = mergeTwoListsRecursive(list1.next, list2);
       return list1;
   } else {
       list2.next = mergeTwoListsRecursive(list1, list2.next);
       return list2;
   }
}

public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
   if (list1 == null) {
       return list2;
   }


   if (list2 == null) {
       return list1;
   }


   if (list1.val < list2.val) {
       list1.next = mergeTwoListsRecursive(list1.next, list2);
       return list1;
   } else {
       list2.next = mergeTwoListsRecursive(list1, list2.next);
       return list2;
   }
}

Time and Space Complexity

The time complexity is actually the same regardless of whether you implement this in the recursive or the iterative manner. Since we have to go through all the elements of each list once the time complexity is O(m + n). The space complexity is O(1) for the iterative solution. We only create pointers once in our code and reuse them for the rest of the program. The recursive solution has space complexity of O(m + n) because we can build up a call stack the size of both lists combined.

Key Takeaways

Hopefully this post was enlightening. We explored two ways to merge two sorted linked lists. We also walked through the space and time complexities of each solution. Although this is a simple problem it is foundational for understanding more complex algorithms like merge sort which are used in more advanced LeetCode problems.