@qddpx Amazing solution, you just made my day with this solution. Thank you :)
RepentThySins
@RepentThySins
Posts made by RepentThySins

RE: A different O(n) approach  easy to understand and simple code

Easy to Understand solution with Code
public class Solution { public double myPow(double base, int power) { if(power > 0){ return calculatePower(base,power); }else if(power < 0){ return 1/calculatePower(base, power); }else{ return 1; } } public double calculatePower(double base, int power){ if(power == 0){ return 1; }else if(power == 1){ return base; } double inter = calculatePower(base,power/2); if(power%2 == 0){ return inter*inter; }else{ return inter*inter*base; } } }

Simple clear explanation of Solution with Simple code to Understand
The solution for this problem is pretty Simple. All the solutions I have seen so far do not provide much explanation. My explanation is for people like me, who are trying to understand the solution rather than writing extremely short code to reduce the number of lines. So here is the solution.
In the given problem, we need to find the first positive number that is missing. We consider this number to be greater than zero. The input array also contains negative numbers. The main idea behind this solution is that, we try to put the numbers in their right indices. if we want to keep an element A[i] in its right place, we keep it at index A[i]1 because Arrays are Zero indexed.
Now when we scan the array, there are two conditions. the number is positive or negative.
 If the number is negative we just ignore it.
 If the number is positive, we have four cases.
a. if the number A[i] is greater than the length of the array, we cannot keep it in its right index ie., A[i]1. So we just increment the counter.
b. if the number A[i] is already at the right index, that is A[i] == i+1, we just increment the counter.
c. if the number is a duplicate and the correct number is already in the right place, ie., A[i] == A[A[i]1], we just increment the counter.
d. finally, if none of the above cases satisfy, it means that this number must be placed in the correct place. So we swap it with the number at A[i]1;
Now the number at A[i]1 can belong to two types.
a. Zero or A negative number
b. This number is greater than the length of the given array.when we keep doing this swap, at the location of missing number, either of the above mentioned numbers would be present, making us easy to identify the missing number. Here is the code for the same.
public class Solution { public int firstMissingPositive(int[] A) { int i= 0; while(i < A.length){ if(A[i] <= 0){ i++; }else{ if(A[i] > A.length){ i++; }else if(A[i] == i+1){ i++; }else if(A[i] == A[A[i]1]){ i++; }else{ swap(A, i, A[i]1); } } } i=0; while(i < A.length && A[i] == i+1){ i++; } return i+1; } private void swap(int[] A, int i, int j){ int temp = A[i]; A[i] = A[j]; A[j] = temp; } }
Thanks,

DP Solution for Triangle including clear explanation and picture representation
This problem is a very good implementation of DP and can be solved using only O(n) extra space. But it is quite difficult to imagine or visualize the solution to this problem. Even if one finds the code, it will be difficult to understand the code and why they are doing it, the way they are doing it. So I am trying to explain the thought process behind the backward, DP solution.
Lets take the triangle given in the example.
[2],
[3,4],
[6,5,7],
[4,1,8,3]To find the Minimum Path sum, we can visualize the above triangle in this format.
2 / \ 3 4 / \ / \ 6 5 7 / \ / \ / \ 4 1 8 3
Now once we visualize the triangle as the tree above, we can start processing it to find the min sum path.
6 in row 3 can reach the row number 4 either through 4 or 1, and it will be minimum if it chooses 1, similarly 5 in row number 3 can reach row number 4 either through 1 or 8. Since we want minimum, we choose 1 and finally 7 in row number 3 can reach row number 4 either through 8 or 3. Since we want minimum we choose 3.
So after first iteration, our result array would be 7,6,10,3. ( please see the code to understand what is result array).
Code:
int[] result = new int[triangle.size()]; for(int i=0;i < currentList.size(); i++){ result[i] = currentList.get(i); } for(int i=triangle.size()2; i >=0 ;i){ currentList = triangle.get(i); for(int j=0;j < currentList.size();j++){ result[j] = Math.min(result[j], result[j+1]) + currentList.get(j); } } return result[0];
Please comment if you have any questions.