I am confused when dealing with arithmetic around array indices, majorly around the corner cases.

For ex:

• Finding word in text ( search of needle in haystack). In following, it should be i <= hayStackTill instead of <

    public int search(char[] haystack, char[] needle) {
            int hayStackTill = haystack.length - needle.length;
            for(int i = 0; i < hayStackTill; i++) // it should be i <= hayStackTill instead of <
    }

• Given the size of array and count from last, Find the index from start

   int index = a.length - countFromLast; // it should be instead a.length - countFromLast + 1

• Also, here https://youtu.be/KMBe8Lhhti8?t=12319 Mimino suggests to use +7 , because there is chance of index out of bounds. which is needed only if you don't estimate array indices properly.

Can anyone help with some practice problems around this ( Also any suggestions are welcome).

While the Codechef MNMX problem is easy, I am trying to solve it by changing the constraint to following.

Select a pair of adjacent integers and remove the **smaller** one and keeping the larger one. And the cost is larger one( while the original problem removes the **larger** one) 

In original problem, We are removing the larger one and keeping the smaller one, so We can start with smaller one and do it n-1 times. So the sum_of_cost = (n-1) * min_element

How to solve it if we change the constraint to remove smaller one and keep larger one, and the cost is the larger one ?

I couldn't find upper_bound equivalent in java. Is there any alternative function that I can use ?

PS: I did google this

From the problem statement ( Contest is over)

Two boomerang constellations are distinct if they are not made up of the same unordered pair of line segments

What does above mean?

How to solve this problem if the restriction is changed to "if they are made up of same Ordered pair of the line segment" instead of "unordered" ( without hashmap to keep track that we have see it earlier ) ?

I came up with following problem, Like in Any Townhouse, There are M Row houses in N lines. And a row house is a form of rectangle. In this case, Row houses are form of rectangles but not with fixed sizes, with No fixed spacing from neighbour houses AND No fixed spacing from one row to other. The Problem is given a point, We need to locate respective row house. And we want to optimize the queries ( locate a point to the respective house) as houses are laid once.

I can always check all the houses if the given point belongs to that house. But, the optimisation I am looking for is how to avoid looking at the some of the houses. For example, I can do binary search on one house (call it M1 ) and it's right house and left house, If the distance to point is reduced with left house compared to M1, then we go toward left otherwise right. But, this seems to not to work, Can you please help.

And to make it complex, What if the row house can take any arbitrary shape. Are there any similar problems in any online judge ?

PS: This question is still not answered , so any help is appreciated.

EDIT: In the earlier edit the row houses are of fixed sizes, I changed that constraint.

Can you please point me to some practice prolems ( on any Online judge) on "K nearest points to origin" It is one time query, But also how can I solve if it's for multiple queries ?

Given an Array N unique elements ,and some elements may contain values greater than N.

For ex: 1, 8, 2147483647

To work on Fenwick Tree, we need to adjust that to a 1 — N range. Is there a way to do this ?

Codeforces Round 313 Problem A: Currency System in Geraldion

How to solve if we rephrase the problem statement to find " Minimum unfortunate sum that is greater than 1 "?

If the input notes denomination includes "1", obviously there won't be any "unfortunate sum".

How to solve "Largest product in a grid" Project Euler#11 using direction array.

As Copy pasting the code for each direction is error prone, How can it be solved using direction array ?

I came up a solution for the following problem.

But, I want to do it in true recursive way. Can you help with coming up with Pair<int,int> or Object.

Problem:

Given a binary tree, find the maximum path sum. It can contain -ve values

The path may start and end at any node in the tree. For example: Given the below binary tree,

       1
      / \
     2   3

Return 6.

Given the below binary tree,

       -2
         \
         -1

Return -1.

Solution with Global variable way:

int max = Integer.MIN_VALUE
public int calculateSum(TreeNode root) {
	if (root == null)
		return 0;

	int left = calculateSum(root.left, max);
	int right = calculateSum(root.right, max);

	int current = Math.max(root.val, Math.max(root.val + left, root.val + right));

	max = Math.max(max, Math.max(current, left + root.val + right));

	return current;
}

The general understanding is that we can't use DFS in graph for finding shortest path.

But, I am having difficult time understanding why the DFS works for following problem, even though a node can be reached in multiple ways. https://oj.leetcode.com/problems/triangle/

Also,What kind of shortest path problems can be solved with DFS ?

I understand that we can use Uniform Cost search ( similar one Dijkstra) for finding shortest path.

Solution with DFS for above problem:

public class Solution {
    int[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new int[triangle.size()][triangle.size()];
        for(int i = 0; i < triangle.size(); i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }
        return minimumTotal(triangle,0,0);
    }
    public int minimumTotal(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() -1)
           return triangle.get(i).get(j); // base case
        //if(memo[i][j] != INTEGER.MIN_VALUE) {
        //    return memo[i][j];
        //}
        int sum0 = minimumTotal(triangle, i+1, j);
        int sum1 = minimumTotal(triangle, i+1, j+1);
        int res = Math.min(sum0, sum1) + triangle.get(i).get(j);
        memo[i][j] = res;
        return res;
    }   
}

PS: If you think the problem doesn't have a goal state, We can modify the problem to have a goal state, For ex. To reach some indexed position from the top row.

And, We could still use DFS for it.

My Question is more towards following, How to define the boundary for shortesr path priblems solvable on graph using DFS

EDIT For followup Question:

Thanks for the clarifications :)

But, One follow-up question is that, In this problem https://oj.leetcode.com/problems/triangle/, you can reach a node in different ways, but it can be solvable with DFS.

public class Solution {
    int[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new int[triangle.size()][triangle.size()];
        for(int i = 0; i < triangle.size(); i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }
        return minimumTotal(triangle,0,0);
    }
    public int minimumTotal(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() -1)
           return triangle.get(i).get(j); // base case
        if(memo[i][j] != INTEGER.MIN_VALUE) {
            return memo[i][j];
        }
        int sum0 = minimumTotal(triangle, i+1, j);
        int sum1 = minimumTotal(triangle, i+1, j+1);
        int res = Math.min(sum0, sum1) + triangle.get(i).get(j);
        memo[i][j] = res;
        return res;
    }   
}

=====================================================================

Original post:

Why we cannot use DFS to find the shortest distance on the graph/mazes, while it can be used on the tree.

How can I formally prove that even a modified DFS doesn't work.

For ex: we can solve this one ( https://oj.leetcode.com/problems/triangle/) easily with DFS.

Thanks for your help !!!

I am trying to solve this problem with recursive DFS and Memoization.

How to solve this ? Is it possible to do it with DFS ?