Daily Coding Problem 260 : Reconstruct a jumbled array - Intuition?

Question

I'm going through the question below.

The sequence [0, 1, ..., N] has been jumbled, and the only clue you have for its order is an array representing whether each number is larger or smaller than the last. Given this information, reconstruct an array that is consistent with it.

For example, given [None, +, +, -, +], you could return [1, 2, 3, 0, 4].

I went through the solution on this post but still unable to understand it as to why this solution works. I don't think I would be able to come up with the solution if I had this in front of me during an interview. Can anyone explain the intuition behind it? Thanks in advance!

Answer 1

This answer tries to give a general strategy to find an algorithm to tackle this type of problems. It is not trying to prove why the given solution is correct, but lying out a route towards such a solution.

A tried and tested way to tackle this kind of problem (actually a wide range of problems), is to start with small examples and work your way up. This works for puzzles, but even so for problems encountered in reality.

First, note that the question is formulated deliberately to not point you in the right direction too easily. It makes you think there is some magic involved. How can you reconstruct a list of N numbers given only the list of plusses and minuses?

Well, you can't. For 10 numbers, there are 10! = 3628800 possible permutations. And there are only 2⁹ = 512 possible lists of signs. It's a very huge difference. Most original lists will be completely different after reconstruction.

Here's an overview of how to approach the problem:

• Start with very simple examples
• Try to work your way up, adding a bit of complexity
• If you see something that seems a dead end, try increasing complexity in another way; don't spend too much time with situations where you don't see progress
• While exploring alternatives, revisit old dead ends, as you might have gained new insights
• Try whether recursion could work:
  • given a solution for N, can we easily construct a solution for N+1?
  • or even better: given a solution for N, can we easily construct a solution for 2N?
• Given a recursive solution, can it be converted to an iterative solution?
• Does the algorithm do some repetitive work that can be postponed to the end?
• ....

So, let's start simple (writing 0 for the None at the start):

• very short lists are easy to guess:
  • '0++' → 0 1 2 → clearly only one solution
  • '0--' → 2 1 0 → only one solution
  • '0-+' → 1 0 2 or 2 0 1 → hey, there is no unique outcome, though the question only asks for one of the possible outcomes
• lists with only plusses:
  • '0++++++' → 0 1 2 3 4 5 6 → only possibility
• lists with only minuses:
  • '0-------'→ 7 6 5 4 3 2 1 0 → only possibility
• lists with one minus, the rest plusses:
  • '0-++++' → 1 0 2 3 4 5 or 5 0 1 2 3 4 or ...
  • '0+-+++' → 0 2 1 3 4 5 or 5 0 1 2 3 4 or ...
  • → no very obvious pattern seem to emerge
• maybe some recursion could help?
  • given a solution for N, appending one sign more?
  • appending a plus is easy: just repeat the solution and append the largest plus 1
  • appending a minus, after some thought: increase all the numbers by 1 and append a zero
  • → hey, we have a working solution, but maybe not the most efficient one
    • the algorithm just appends to an existing list, no need to really write it recursively (although the idea is expressed recursively)
    • appending a plus can be improved, by storing the largest number in a variable so it doesn't need to be searched at every step; no further improvements seem necessary
    • appending a minus is more troublesome: the list needs to be traversed with each append
      • what if instead of appending a zero, we append -1, and do the adding at the end?
      • this clearly works when there is only one minus
      • when two minus signs are encountered, the first time append -1, the second time -2
      • → hey, this works for any number of minuses encountered, just store its counter in a variable and sum with it at the end of the algorithm

This is in bird's eye view one possible route towards coming up with a solution. Many routes lead to Rome. Introducing negative numbers might seem tricky, but it is a logical conclusion after contemplating the recursive algorithm for a while.