Road to Genius: advanced #38

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function LVP(s) {
  let arr = new Array()
  let LG = 0
  arr.push(-1)
  for(let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      arr.push(i)
    } else {
      arr.pop()
      if (arr.length === 0) {
        arr.push(i)
      } else {
        LG = Math.max(LG, i - arr[arr.length-1])
      }
    }
  }
  return LG
}

let A = LVP('(((())(())()');

// A = ? (number)

We have encountered this code before many episodes ago (spoiler! here: https://dev.to/codr/road-to-genius-smart-25-144l) but this time we have to fully analyze it to solve it. I already know the answer because I know what the code does, yet let's take a look at it.

We have to figure out A's value (number) which is the output of:

A = LVP('(((())(())()')

After a quickly glimpse at the code, it has something to do with the parentheses, most likely syntax validation. The most important object to track in this function is arr, because everything seems to rely on it.

To understand what the code actually does, let's keep track of arr in pseudo-code:

s = '(((())(())()'
LG = 0
arr = [-1]

for each "i" in "s":

i0 == (
arr = [-1, 0] --> push

i1 == (
arr = [-1, 0, 1] --> push

i2 == (
arr = [-1, 0, 1, 2] --> push

i3 == )
arr = [-1, 0, 1] --> pop
LG = max(0, 3-1) = 2

i4 == )
arr = [-1, 0] --> pop
LG = max(2, 4-0) = 4

i5 == (
arr = [-1, 0, 5] --> push

i6 == (
arr = [-1, 0, 5, 6] --> push

i7 == )
arr = [-1, 0, 5] --> pop
LG = max(4, 7-5) = 4

i8 == )
arr = [-1, 0] --> pop
LG = max(4, 8-0) = 8

i9 == (
arr = [-1, 0, 9] --> push

i10 == )
arr = [-1, 0] --> pop
LG = max(8, 10-0) = 10

return LG=10

--> A = 10

Just like that we've found that A=10:

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/