Posted on

Maximum Binary Tree — LeetCode #654

Hello. Thought I’d make it a habit by writing (hopefully) weekly on some coding challenge I work on in my free time. So, welcome to the second article :). Today’s challenge is not actually that much different than the previous one (well, it is different, but not that different). Let’s take a look at Maximum Binary Tree challenge on LeetCode.

The problem is on LeetCode and of difficulty: medium.

Problem Statement

The problem is simple: finding the maximum binary tree that can be formed by the given array. I’ll explain more…

You’re given an array, for example, [3,2,1,6,0,5]. The Maximum Binary tree is defined in the problem statement as:

the tree with the root being the maximum value in the array

Well, this means that obviously our maximum element in the given array currently is 6. So, let’s make this our binary tree root.

After picking 6, the problem states that:

The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.

The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

I believe this screamed recursion at my face!

The Algorithm

This basically means that, after picking the max element, 6, we’ll split the array into: [3, 2, 1] (6 was here) and [0, 5]

We will repeat what we did. For (sub)array [3, 2, 1], we’ll:

  • pick the max: 3, make it the (sub)tree node
  • split the array into [], [2, 1]
  • pick the max: 2
  • split the array into: [], [1]
  • pick the max: 1
  • no more work.

Our tree now looks like this:

Why are there nulls?

Remember that in recursive algorithms, we need a stopping condition (base case). Otherwise, our recursion will run forever until stack overflows!

Alright, back to the problem. We walked through the recursive algorithm and we sank into the left subtree. If we backtrack and do the same for the remaining [0, 5] part of the array, the tree should look like this:

Nulls removed for readability.

Complexity

If the current maximum element of a subarray is always in the middle of that subarray, we would have a balanced tree, giving O(log n)since we would have n levels.

In every construction, we would loop on array[start… end] which is a linear, O(n) algorithm. Which gives us, in best condition, O(n log n)

Yet, in average and worst cases, the array isn’t in a specific order, so we might end up with an unbalanced tree which would give us the same time as a linked list: O(n) * O(n) (for calculating max) = O(n²).

Implementation in Java

I’ll leave the explanation in the code comments.

Note: Of course there are more ways to approach this problem, but this is the one I thought easiest to follow.

References

Posted on

Keys and Rooms — LeetCode Coding Challenge

Algorithmic challenge - a boy holding head in pain seeing directed, curved line segments moving around.

Hello, world. I have been brushing up on algorithms and data structures and a big part of what I do is working on solving some LeetCode and HackerRank challenges. I wanted to stay in the ready-for-interview mode for sometime. Who knows when an opportunity may come!

I encountered this problem: Keys and Rooms. Despite not solving many challenges related to graphs before, I felt that this challenge was a good way to start hacking into solving programming challenges that are based on graphs and their algorithms.

Problem Statement

Firstly, let’s look at the description. Which is straight forward: there are N rooms (named 0, 1, … N-1). Each room contains keys for other number of rooms. For example, room 0 could contain keys for rooms 1, 3.

If we could start going into one of the rooms, let’s say room 0, how do you think we make sure that all the rooms are reachable?

For example:

Input: [[1],[2],[3],[]]

Keys in room 0: {1}
Keys in room 1: {2}
Keys in room 2: {3}
Keys in room 3: {} (no keys)

Output: true

We go to room #0, we find a key to room #1. We go to room #1, we find a key to room #2. We go to room #2, we find a key to room #3. We go to room #3, we find no keys.

Eventually, we find out that the output is true because we could visit each and every room at least once.

How I solved it

It was really simple. Depth-first search. Think of the rooms as nodes in a graph, and the only way to move from one node (room) to another is an edge (key).

DFS (iterative version) pseudocode:

  procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
          v = S.pop()
          if v is not labeled as discovered:
              label v as discovered
              for all edges from v to w in G.adjacentEdges(v) do 
                  S.push(w)

We model the rooms as nodes, the keys as edges to the rooms designated by the value of the key. For instance, in the example: [[1,3],[3,0,1],[2],[0]] we build a graph of [0, N-1] nodes. That is, rooms: [0, 1, 2, 3]. For each node (room), we create an edge connecting the current room with the room referenced by the value of the key.

[[1,3],[3,0,1],[2],[0]]

As we can see, room 2 contains a key only to itself and there’s no other room that contains a key to room 2. Hence, output should be false since there is at least one room we cannot visit.

The coding part

To sum up, I find it was a great experience to write about solving a challenge. Not just “solving a challenge”, but rather, the actual writing about the solution. Researching the algorithm, brushing up on Java for implementation and on algorithms to ensure the correctness of the expalnation, it really adds a lot.

Finally, as I first said, I believe it makes a person learn more about the topic they are writing about when they actually start to write.

I will try to make this a habit and probably keep solving interesting challenges and write about them, explaining the approach and the algorithm behind solving.

References