Find dropping point of an egg

Posted in

Find dropping point of an egg
vinaykhatri

Vinay Khatri
Last updated on May 30, 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]

    Sample Output

    [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:

    Leave a Comment on this Post

    0 Comments