CODEWITHSUNDEEP
arraysdata-structures
Paritosh M
Paritosh M

Reputation: 379

Need help to solve challenging Data structure problem

I came across this problem where given an array of integers, tell if the sequence of integers will exit the array from left, right or deadend. You enter the array from the left and move N indices(where N is the value of the integer) in the specified direction(positive is right, negative is left)

Examples
[1,1,1] -> Exits Right
[1,-2]=> Exits Left
[2,0,-1]-> Deadends
[2,5,1,-2,0]-> Exits Right

One solution which comes to my mind is if value of all integers are positive then Exits Right or Exits Left. However this solution does not cover all the scenario. I need help to solve this problem.

Upvotes: 0

Views: 57

Answers (2)

x4k3p
x4k3p

Reputation: 1779

Here some hacky golang:

package main

import (
  "fmt"
)

func WhereIsTheExit(arr []int) {
  
  if (len(arr) == 0) {
    fmt.Println("No elements")
    return
  } 

  i := arr[0]

  for p := 1; p < len(arr); p++ {

    fmt.Printf("Current value: %d\n", i)

    if (i > len(arr) - 1 || i < 0) {
      break
    }

    i += arr[i]

    fmt.Printf("Next value: %d\n", i)
  }

  if (i >= len(arr)) {
    fmt.Println("====> right")
  } else if (i < 0) {
    fmt.Println("====> left")
  } else {
    fmt.Println("====> deadend")
  }
}

func main() {

  empty := []int{}
  deadend := []int{1,2,0,-3}
  deadend2 := []int{1,0,-1}
  right := []int{2,0,3,0,0}
  right2 := []int{1,2,0,4,0,2,7,1}
  left := []int{1,-2}
  left2 := []int{1,2,0,3,0,0,-10}

  WhereIsTheExit(empty)
  WhereIsTheExit(deadend)
  WhereIsTheExit(deadend2)
  WhereIsTheExit(right)
  WhereIsTheExit(right2)
  WhereIsTheExit(left)
  WhereIsTheExit(left2)
}

Try out: https://play.golang.org/p/KU4mapYf_b3

Upvotes: 1

Rajesh
Rajesh

Reputation: 24955

You can do this:

  • Create a variable to hold index position and initialize it with first value
  • Loop over array and on every iteration, compute new value of index by adding value of pointed index.
  • At the end of loop, check:
    • Right: If index >= array.length`
    • Left: if index < 0
    • Deadend: If index is in bounds

Based on this, below is an example using Javascript:

function printDirection(arr) {
  let index = arr[0];
  for (let i = 1; i < arr.length; i++) {
    /**
     * Below condition covers following cases:
     * 1. If the value is undefined. This will happen if index is out of bound
     * 2. If value is 0. In this case, `index` will never change and remaining iterations can be skipped
     */
    if (!arr[index]) break;
    index += arr[index]
  }
  if (index >= arr.length) {
    console.log('Exit Right')
  } else if (index < 0) {
    console.log('Exit Left')
  } else {
    console.log('Deadend')
  }
}

const data = [
  [1, 1, 1],
  [1, -2],
  [2, 0, -1],
  [2, 5, 1, -2, 0],
]
data.forEach((arr) => printDirection(arr))

Upvotes: 2

Related Questions