# Find dropping point of an egg

Posted in

Vinay Khatri
Last updated on September 10, 2024

## Problem

You are given a 2-D grid where each cell has a value of either 1 or -1. Each cell in the box has a diagonal board that spans two corners and can redirect an egg to the right or left. A board that redirects the egg to the right spans the top-left corner to the bottom-right corner and is denoted by the number 1 in the grid. A board that redirects the egg to the left spans the top-right corner to the bottom-left corner of the grid and is represented as -1.

We place one egg at the top of each box column. Each egg has the potential to become stuck in the box or fall out of the bottom. If an egg strikes a "V" shaped pattern between two boards or if a board redirects the egg into either wall of the box, it becomes stuck. The task is to return a list of columns where ith value will denote the value of the column where the egg will drop if it starts from ith column. Below is an example of the mechanism for the matrix [1, 1, -1] [1, 1, 1]

E1 will leave the grid from column 2, while E2 and E3 will both get stuck in the “V” position

#### Sample Input

```[1, 1, -1]
[1, 1, 1]```

[2, -1, -1]

## Approach

When we are at a cell (row, col) that has the val value 1, this cell will take us to the cell (row+1, col+1), while if we are at a cell (row, col) that has the value -1, this cell will take us to the cell (row+1, col-1). We keep taking the egg down according to the above conditions. We just need to handle the cases below, as they will block the egg from going down. If we find any of the below conditions, while we are a cell, we cannot go beyond the current cell.

1. If the cell is -1 and we are at the 0th column, we cannot go beyond.
2. If the cell is 1 and we are at the last column, we cannot go beyond.
3. If we are at -1 and the left cell is 1, this is a “V” state, we cannot go beyond.
4. If we are at 1 and the right cell is -1, this is a “V” state, we cannot go beyond.

### Complexity Analysis

The time complexity is O(MXN) and the space complexity is O(N).

C++ Programming

```#include<bits/stdc++.h>
using namespace std;

// function to get finishing columns
vector<int> solve(vector<vector<int>>& grid) {

int m = grid.size(), n = grid[0].size();
vector<int> res;

// iterate through columns
for (int i = 0; i < n; ++i) {
int col = i, i2;

// iterate diagonally
for (int j = 0; j < m; ++j) {
i2 = col + grid[j][col];
// check condition
if (i2 < 0 || i2 >= n || grid[j][i2] != grid[j][col]) {
col = -1;
break;
}
col = i2;
}
res.push_back(col);
}
return res;
}

int main()
{
vector<vector<int>>grid {{1, 1, -1}, {1, 1, 1}};

vector<int>ans = solve(grid);

for(auto itr: ans) cout<<itr<<" ";
}```

#### Output

```2 -1 -1

```

Java Programming

```class Solution
{

// function to get finishing columns
public static int[] solve(int[][] grid) {
int m = grid.length, n = grid[0].length, res[] = new int[n];

// iterate through columns
for (int i = 0; i < n; ++i) {
int col = i, i2;

// iterate diagonally
for (int j = 0; j < m; ++j) {
i2 = col + grid[j][col];

// check condition
if (i2 < 0 || i2 >= n || grid[j][i2] != grid[j][col]) {
col = -1;
break;
}
col = i2;
}

res[i] = col;
}
return res;
}

public static void main(String[] args)
{
int[][] grid = new int[2][3];
grid[0][0] = 1;
grid[0][1] = 1;
grid[0][2] = -1;
grid[1][0] = 1;
grid[1][1] = 1;
grid[1][2] = 1;
int[] ans = solve(grid);

for(int i=0;i<3;i++) System.out.print(ans[i]+" ");

}
}```

#### Output

```2 -1 -1

```

#### Python Programming

```# function to get finishing columns
def solve(grid):
m, n = len(grid), len(grid[0])

def test(i):
# iterate diagonally
for j in range(m):
i2 = i + grid[j][i]

# check condition
if i2 < 0 or i2 >= n or grid[j][i2] != grid[j][i]:
return -1
i = i2
return i

return map(test, range(n))

grid = [[1, 1, -1], [1, 1, 1]]

for i in solve(grid):
print(i, end=" ")```

#### Output

`2 -1 -1`

People are also reading: