Skip to main content

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-

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