Skip to main content

Unique path


A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?







Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
 Solution-




Comments

Post a Comment

Popular posts from this blog

Java 8- Sorting a hashmap (by key and by value) using lambda expression and streams

Sometimes while working on business problems, it’s very common to come across use cases wherein a map needs to be sorted by either keys or by values. In this post, we will cover some of the examples to sort a map of primitives and custom objects.   In below approaches, we will not destroy existing map and will create a new map to ensure consistency of sorting 1. Sort HashMap by key  In order to sort a map by key, all we need to do is to use sorted method of stream interface and pass a default default/custom comparator to it. Moreover, to sort by keys, we need to use comparingByKey method of Entry interface of Map. 2. Sort HashMap by values  In order to sort a map by key, all we need to do is to use sorted method of stream interface and pass a default default/custom comparator to it. Moreover, to sort by keys, we need to use comparingByValue method of Entry interface of Map.
Post a Comment
Read more

Walls and gates- Find shortest distances between rooms and gates

Leetcode: Walls and Gates You are given a  m x n  2D grid initialized with these three possible values. -1  - A wall or an obstacle. 0  - A gate. INF  - Infinity means an empty room. We use the value  2 31  - 1 = 2147483647  to represent  INF  as you may assume that the distance to a gate is less than 2147483647 . Fill each empty room with the distance to its  nearest  gate. If it is impossible to reach a gate, it should be filled with  INF . For example, given the 2D grid: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF After running your function, the 2D grid should be: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 Understand the problem: It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution. Below is a DFS solution-
Post a Comment
Read more

Maximum/minimum path sum for a triange

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [      [ 2 ],     [ 3 ,4],    [6, 5 ,7],   [4, 1 ,8,3] ] The minimum path sum from top to bottom is  11  (i.e.,  2  +  3  +  5  +  1  = 11). Note: Bonus point if you are able to do this using only  O ( n ) extra space, where  n  is the total number of rows in the triangle. Solution-
Post a Comment
Read more