Given an array of list of commands U(Up), D(Down), L(Left) and R(Right) and initial cell position (x, y) in a matrix. Find the final cell position of the object in the matrix after following the given commands. It is assumed that the final required cell position exists in the matrix.
Examples:
Input : command[] = "DDLRULL" x = 3, y = 4 Output : (1, 5) Input : command[] = "LLRUUUDRRDDDULRLLUDUUR" x = 6, y = 5 Output : (6, 3)
Source: Flipkart Interview (SDE-1 On Campus).
Approach:
Following are the steps:
- Count cup, cdown, cleft and cright for U(Up), D(Down), L(Left) and R(Right) movements respectively.
- Calculate final_x = x + (cright – cleft) and final_y = y + (cdown – cup).
The final cell position is (final_x, final_y)
Implementation:
C++
// C++ implementation to find the final cell position // in the given matrix #include <bits/stdc++.h> using namespace std; // function to find the final cell position // in the given matrix void finalPos( char command[], int n, int x, int y) { // to count up, down, left and cright // movements int cup, cdown, cleft, cright; // to store the final coordinate position int final_x, final_y; cup = cdown = cleft = cright = 0; // traverse the command array for ( int i = 0; i < n; i++) { if (command[i] == 'U' ) cup++; else if (command[i] == 'D' ) cdown++; else if (command[i] == 'L' ) cleft++; else if (command[i] == 'R' ) cright++; } // calculate final values final_x = x + (cright - cleft); final_y = y + (cdown - cup); cout << "Final Position: " << "(" << final_x << ", " << final_y << ")" ; } // Driver program to test above int main() { char command[] = "DDLRULL" ; int n = ( sizeof (command) / sizeof ( char )) - 1; int x = 3, y = 4; finalPos(command, n, x, y); return 0; } |
Java
// Java implementation to find // the final cell position // in the given matrix import java.util.*; import java.lang.*; import java.io.*; class GFG { // function to find the // final cell position // in the given matrix static void finalPos(String command, int n, int x, int y) { // to count up, down, left // and cright movements int cup, cdown, cleft, cright; // to store the final // coordinate position int final_x, final_y; cup = cdown = cleft = cright = 0 ; // traverse the command array for ( int i = 0 ; i < n; i++) { if (command.charAt(i) == 'U' ) cup++; else if (command.charAt(i) == 'D' ) cdown++; else if (command.charAt(i)== 'L' ) cleft++; else if (command.charAt(i) == 'R' ) cright++; } // calculate final values final_x = x + (cright - cleft); final_y = y + (cdown - cup); System.out.println( "Final Position: " + "(" + final_x + ", " + final_y + ")" ); } // Driver Code public static void main(String []args) { String command = "DDLRULL" ; int n = command.length(); int x = 3 , y = 4 ; finalPos(command, n, x, y); } } // This code is contributed // by Subhadeep |
Python3
# Python3 implementation to find # the final cell position # in the given matrix # function to find the # final cell position # in the given matrix def finalPos(command, n, x, y): cup = 0 cdown = 0 cleft = 0 cright = 0 ; # traverse the command array for i in range (n): if (command[i] = = 'U' ): cup + = 1 elif (command[i] = = 'D' ): cdown + = 1 elif (command[i] = = 'L' ): cleft + = 1 elif (command[i] = = 'R' ): cright + = 1 # calculate final values final_x = x + (cright - cleft); final_y = y + (cdown - cup); print ( "Final Position:" , "(" , final_x, "," , final_y, ")" ); # driver code command = "DDLRULL" ; n = len (command); x = 3 y = 4 ; finalPos(command, n, x, y); # This code is contributed by phasing17 |
C#
// C# implementation to find // the final cell position // in the given matrix class GFG { // function to find the // final cell position // in the given matrix static void finalPos( string command, int n, int x, int y) { // to count up, down, left // and cright movements int cup, cdown, cleft, cright; // to store the final // coordinate position int final_x, final_y; cup = cdown = cleft = cright = 0; // traverse the command array for ( int i = 0; i < n; i++) { if (command[i] == 'U' ) cup++; else if (command[i] == 'D' ) cdown++; else if (command[i]== 'L' ) cleft++; else if (command[i] == 'R' ) cright++; } // calculate final values final_x = x + (cright - cleft); final_y = y + (cdown - cup); System.Console.WriteLine( "Final Position: " + "(" + final_x + ", " + final_y + ")" ); } // Driver Code public static void Main() { string command = "DDLRULL" ; int n = command.Length; int x = 3, y = 4; finalPos(command, n, x, y); } } // This code is contributed // by mits |
PHP
<?php // PHP implementation to find the final // cell position in the given matrix // function to find the final cell // position in the given matrix function finalPos( $command , $n , $x , $y ) { // to count up, down, left and // cright movements $cup ; $cdown ; $cleft ; $cright ; // to store the final coordinate // position $final_x ; $final_y ; $cup = $cdown = $cleft = $cright = 0; // traverse the command array for ( $i = 0; $i < $n ; $i ++) { if ( $command [ $i ] == 'U' ) $cup ++; else if ( $command [ $i ] == 'D' ) $cdown ++; else if ( $command [ $i ] == 'L' ) $cleft ++; else if ( $command [ $i ] == 'R' ) $cright ++; } // calculate final values $final_x = $x + ( $cright - $cleft ); $final_y = $y + ( $cdown - $cup ); echo "Final Position: " . "(" . $final_x . ", " . $final_y . ")" ; } // Driver Code $command = "DDLRULL" ; $n = strlen ( $command ); $x = 3; $y = 4; finalPos( $command , $n , $x , $y ); // This code is contributed // by Akanksha Rai |
Javascript
<script> // JavaScript implementation to find // the final cell position // in the given matrix // function to find the // final cell position // in the given matrix function finalPos(command, n, x, y) { // to count up, down, left // and cright movements let cup, cdown, cleft, cright; // to store the final // coordinate position let final_x, final_y; cup = cdown = cleft = cright = 0; // traverse the command array for (let i = 0; i < n; i++) { if (command[i] == 'U' ) cup++; else if (command[i] == 'D' ) cdown++; else if (command[i]== 'L' ) cleft++; else if (command[i] == 'R' ) cright++; } // calculate final values final_x = x + (cright - cleft); final_y = y + (cdown - cup); document.write( "Final Position: " + "(" + final_x + ", " + final_y + ")" ); } // driver code let command = "DDLRULL" ; let n = command.length; let x = 3, y = 4; finalPos(command, n, x, y); </script> |
Output
Final Position: (1, 5)
Complexity Analysis:
- Time Complexity: O(n), where
is the number of commands.
- Space complexity: O(1) since using constant variables
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!