Data Modelling & AI Data Structure & Algorithm

Coordinates of the last cell in a Matrix on which performing given operations exits from the Matrix

23 June 2025

0

Given a binary matrix of dimensions N * M, the task is to find the indices of the matrix such that traversal of the given matrix from the cell (0, 0) leads to outside the matrix as per the following conditions:

If the value of arr[i][j] is 0, then traverse in the same direction and check the next value.
If the value of arr[i][j] is 1, then update arr[i][j] to 0 and change the current direction from up, right, down, or left to the directions right, down, left, and up respectively.

Examples:

Input: arr[] = {{0, 1}, {1, 0}}
Output: (1, 1)
Explanation:
Below is the image to illustrate the simulation:

Input: arr[] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 1, 0, 0}}
Output: (2, 0)

Approach: Follow the steps below to solve the problem:

- Initialize two variables, say current_i and current_j, both as 0.
- Traverse the matrix from the index (0, 0) and set the current direction as a right as R.
  - If the value of current_i or current_j is N or M respectively, then perform the following operations:
  - If the value of arr[i][j] is 0, then traverse in the same direction and check the next value.
  - Otherwise, update arr[i][j] to 0 and choose a direction that is right to the current direction. If the direction which is right to the current direction is:
    - L: Move the current row backward i.e., j – 1.
    - R: Move the current row forwards i.e., j + 1.
    - U: Move the current column upwards i.e., i – 1.
    - D: Move the current column downwards i.e., i + 1.
  - If the new coordinates are not within the range, then print the current coordinates as the resulting coordinates and break out of the loop.

C++

// CPP program for the above approach 
#include<bits/stdc++.h>
using namespace std;
 
// Function to check if the indices (i, j) 
// are valid indices in a Matrix or not 
bool issafe(int m, int n, int i, int j)
{
 
  // Cases for invalid cells 
  if (i < 0) 
    return false;
  if (j < 0) 
    return false;
  if (i >= m) 
    return false;
  if (j >= n)
    return false;
 
  // Return true if valid 
  return true;
}
 
// Function to find indices of cells 
// of a matrix from which traversal 
// leads to out of the matrix 
pair<int,int> endpoints(vector<vector<int>> arr, int m, int n){
 
  // Starting from cell (0, 0), 
  // traverse in right direction 
  int i = 0;
  int j = 0;
  int current_i = 0;
  int current_j = 0;
 
  char current_d = 'r';
 
  // Stores direction changes 
  map<char,char> rcd = {{'l', 'u'},{'u', 'r'}, 
                        {'r', 'd'}, 
                        {'d', 'l'}};
 
  // Iterate until the current cell 
  // exceeds beyond the matrix 
  while (issafe(m, n, i, j)){
 
    // Current index 
    current_i = i;
    current_j = j;
 
    // If the current cell is 1 
    if (arr[i][j] == 1){
 
      char move_in = rcd[current_d]; 
 
      // Update arr[i][j] = 0 
      arr[i][j] = 0;
 
      // Update indices according 
      // to the direction 
      if (move_in == 'u') 
        i -= 1;
      else if(move_in == 'd') 
        i += 1;
      else if(move_in == 'l') 
        j -= 1;
      else if(move_in == 'r') 
        j += 1;
 
      current_d = move_in;
 
    } 
 
    // Otherwise 
    else{
      // Update indices according 
      // to the direction 
      if (current_d == 'u')
        i -= 1;
      else if(current_d == 'd') 
        i += 1;
      else if(current_d == 'l') 
        j -= 1;
      else if(current_d == 'r') 
        j += 1;
    }
  } 
 
  // The exit coordinates 
  return {current_i, current_j}; 
 
} 
 
// Driver Code
int main()
{
 
  // Number of rows 
  int M = 3;
 
  // Number of columns 
  int N = 5;
 
  // Given matrix arr[][] 
  vector<vector<int>> arr{{0, 1, 1, 1, 0}, 
                          {1, 0, 1, 0, 1}, 
                          {1, 1, 1, 0, 0}};
  pair<int,int> p = endpoints(arr, M, N);
 
  cout << "(" << p.first << ", " << p.second << ")" << endl; 
 
} 
 
// This code is contributed by ipg2016107.

Java

// JAVA program for the above approach 
import java.util.HashMap;
import java.util.Map;
 
class GFG
{
 
// Function to check if the indices (i, j) 
// are valid indices in a Matrix or not 
static boolean issafe(int m, int n, int i, int j)
{
 
  // Cases for invalid cells 
  if (i < 0) 
    return false;
  if (j < 0) 
    return false;
  if (i >= m) 
    return false;
  if (j >= n)
    return false;
 
  // Return true if valid 
  return true;
}
 
// Function to find indices of cells 
// of a matrix from which traversal 
// leads to out of the matrix 
static int [] endpoints(int [][]arr, int m, int n){
 
  // Starting from cell (0, 0), 
  // traverse in right direction 
  int i = 0;
  int j = 0;
  int current_i = 0;
  int current_j = 0;
 
  char current_d = 'r';
 
  // Stores direction changes 
  Map<Character,Character> rcd = new HashMap<>();
  rcd.put('l', 'u');
  rcd.put('u', 'r');
  rcd.put('r', 'd');
  rcd.put('d', 'l');
 
  // Iterate until the current cell 
  // exceeds beyond the matrix 
  while (issafe(m, n, i, j)){
 
    // Current index 
    current_i = i;
    current_j = j;
 
    // If the current cell is 1 
    if (arr[i][j] == 1){
 
      char move_in = rcd.get(current_d); 
 
      // Update arr[i][j] = 0 
      arr[i][j] = 0;
 
      // Update indices according 
      // to the direction 
      if (move_in == 'u') 
        i -= 1;
      else if(move_in == 'd') 
        i += 1;
      else if(move_in == 'l') 
        j -= 1;
      else if(move_in == 'r') 
        j += 1;
 
      current_d = move_in;
 
    } 
 
    // Otherwise 
    else{
      // Update indices according 
      // to the direction 
      if (current_d == 'u')
        i -= 1;
      else if(current_d == 'd') 
        i += 1;
      else if(current_d == 'l') 
        j -= 1;
      else if(current_d == 'r') 
        j += 1;
    }
  } 
 
  // The exit coordinates 
  return new int[]{current_i, current_j}; 
 
} 
 
// Driver Code
public static void main(String[] args)
{
 
  // Number of rows 
  int M = 3;
 
  // Number of columns 
  int N = 5;
 
  // Given matrix arr[][] 
  int [][]arr = {{0, 1, 1, 1, 0}, 
                          {1, 0, 1, 0, 1}, 
                          {1, 1, 1, 0, 0}};
  int []p = endpoints(arr, M, N);
 
  System.out.print("(" +  p[0]+ ", " +  p[1]+ ")" +"\n"); 
}
} 
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach 
   
# Function to check if the indices (i, j) 
# are valid indices in a Matrix or not 
def issafe(m, n, i, j): 
   
    # Cases for invalid cells 
    if i < 0: 
        return False
    if j < 0: 
        return False
    if i >= m: 
        return False
    if j >= n: 
        return False
   
    # Return true if valid 
    return True
   
# Function to find indices of cells 
# of a matrix from which traversal 
# leads to out of the matrix 
def endpoints(arr, m, n): 
   
    # Starting from cell (0, 0), 
    # traverse in right direction 
    i = 0
    j = 0
   
    current_d = 'r'
   
    # Stores direction changes 
    rcd = {'l': 'u', 
           'u': 'r', 
           'r': 'd', 
           'd': 'l'} 
   
    # Iterate until the current cell 
    # exceeds beyond the matrix 
    while issafe(m, n, i, j): 
   
        # Current index 
        current_i = i 
        current_j = j 
   
        # If the current cell is 1 
        if arr[i][j] == 1: 
   
            move_in = rcd[current_d] 
   
            # Update arr[i][j] = 0 
            arr[i][j] = 0
   
            # Update indices according 
            # to the direction 
            if move_in == 'u': 
                i -= 1
            elif move_in == 'd': 
                i += 1
            elif move_in == 'l': 
                j -= 1
            elif move_in == 'r': 
                j += 1
   
            current_d = move_in 
   
        # Otherwise 
        else: 
   
            # Update indices according 
            # to the direction 
            if current_d == 'u': 
                i -= 1
            elif current_d == 'd': 
                i += 1
            elif current_d == 'l': 
                j -= 1
            elif current_d == 'r': 
                j += 1
   
    # The exit coordinates 
    return (current_i, current_j) 
   
# Driver Code 
   
   
# Number of rows 
M = 3
   
# Number of columns 
N = 5
   
# Given matrix arr[][] 
arr = [[0, 1, 1, 1, 0], 
       [1, 0, 1, 0, 1], 
       [1, 1, 1, 0, 0], 
       ] 
   
print(endpoints(arr, M, N))

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to check if the indices (i, j)
  // are valid indices in a Matrix or not
  static bool issafe(int m, int n, int i, int j)
  {
 
    // Cases for invalid cells
    if (i < 0)
      return false;
    if (j < 0)
      return false;
    if (i >= m)
      return false;
    if (j >= n)
      return false;
 
    // Return true if valid
    return true;
  }
 
  // Function to find indices of cells
  // of a matrix from which traversal
  // leads to out of the matrix
  static int[] endpoints(int[, ] arr, int m, int n)
  {
 
    // Starting from cell (0, 0),
    // traverse in right direction
    int i = 0;
    int j = 0;
    int current_i = 0;
    int current_j = 0;
 
    char current_d = 'r';
 
    // Stores direction changes
    Dictionary<char, char> rcd
      = new Dictionary<char, char>();
    rcd['l'] = 'u';
    rcd['u'] = 'r';
    rcd['r'] = 'd';
    rcd['d'] = 'l';
 
    // Iterate until the current cell
    // exceeds beyond the matrix
    while (issafe(m, n, i, j)) {
 
      // Current index
      current_i = i;
      current_j = j;
 
      // If the current cell is 1
      if (arr[i, j] == 1) {
 
        char move_in = rcd[current_d];
 
        // Update arr[i][j] = 0
        arr[i, j] = 0;
 
        // Update indices according
        // to the direction
        if (move_in == 'u')
          i -= 1;
        else if (move_in == 'd')
          i += 1;
        else if (move_in == 'l')
          j -= 1;
        else if (move_in == 'r')
          j += 1;
 
        current_d = move_in;
      }
 
      // Otherwise
      else {
        // Update indices according
        // to the direction
        if (current_d == 'u')
          i -= 1;
        else if (current_d == 'd')
          i += 1;
        else if (current_d == 'l')
          j -= 1;
        else if (current_d == 'r')
          j += 1;
      }
    }
 
    // The exit coordinates
    return new int[] { current_i, current_j };
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    // Number of rows
    int M = 3;
 
    // Number of columns
    int N = 5;
 
    // Given matrix arr[][]
    int[, ] arr = { { 0, 1, 1, 1, 0 },
                   { 1, 0, 1, 0, 1 },
                   { 1, 1, 1, 0, 0 } };
    int[] p = endpoints(arr, M, N);
 
    Console.WriteLine("(" + p[0] + ", " + p[1] + ")"
                      + "\n");
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to check if the indices (i, j)
// are valid indices in a Matrix or not
function issafe(m,n,i,j)
{
    // Cases for invalid cells
  if (i < 0)
    return false;
  if (j < 0)
    return false;
  if (i >= m)
    return false;
  if (j >= n)
    return false;
  
  // Return true if valid
  return true;
}
 
// Function to find indices of cells
// of a matrix from which traversal
// leads to out of the matrix
function endpoints(arr,m,n)
{
    // Starting from cell (0, 0),
  // traverse in right direction
  let i = 0;
  let j = 0;
  let current_i = 0;
  let current_j = 0;
  
  let current_d = 'r';
  
  // Stores direction changes
  let rcd = new Map();
  rcd.set('l', 'u');
  rcd.set('u', 'r');
  rcd.set('r', 'd');
  rcd.set('d', 'l');
  
  // Iterate until the current cell
  // exceeds beyond the matrix
  while (issafe(m, n, i, j)){
  
    // Current index
    current_i = i;
    current_j = j;
  
    // If the current cell is 1
    if (arr[i][j] == 1){
  
      let move_in = rcd.get(current_d);
  
      // Update arr[i][j] = 0
      arr[i][j] = 0;
  
      // Update indices according
      // to the direction
      if (move_in == 'u')
        i -= 1;
      else if(move_in == 'd')
        i += 1;
      else if(move_in == 'l')
        j -= 1;
      else if(move_in == 'r')
        j += 1;
  
      current_d = move_in;
  
    }
  
    // Otherwise
    else{
      // Update indices according
      // to the direction
      if (current_d == 'u')
        i -= 1;
      else if(current_d == 'd')
        i += 1;
      else if(current_d == 'l')
        j -= 1;
      else if(current_d == 'r')
        j += 1;
    }
  }
  
  // The exit coordinates
  return [current_i, current_j];
}
 
// Driver Code
// Number of rows
let M = 3;
 
// Number of columns
let N = 5;
 
// Given matrix arr[][]
let arr = [[0, 1, 1, 1, 0],
[1, 0, 1, 0, 1],
[1, 1, 1, 0, 0]];
let p = endpoints(arr, M, N);
 
document.write("(" +  p[0]+ ", " +  p[1]+ ")" +"\n");
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output

(2, 0)

Time complexity: O(m * n)

Space Complexity: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Coordinates of the last cell in a Matrix on which performing given operations exits from the Matrix

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

Philips Hue expands smart lighting lineup with doorbell, string lights, and budget bulbs

Early Galaxy S26 leak hints at one big surprise in the design department

I had trouble playing Hollow Knight: Silksong at release because of how popular it is

US users miss out on the Galaxy S25 FE’s best storage option

EDITOR PICKS

Philips Hue expands smart lighting lineup with doorbell, string lights, and budget bulbs

Early Galaxy S26 leak hints at one big surprise in the design department

I had trouble playing Hollow Knight: Silksong at release because of how popular it is

POPULAR POSTS

Philips Hue expands smart lighting lineup with doorbell, string lights, and budget bulbs

Early Galaxy S26 leak hints at one big surprise in the design department

I had trouble playing Hollow Knight: Silksong at release because of how popular it is

POPULAR CATEGORY

ABOUT US

FOLLOW US