LeetCode - House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Java Solution :

class Solution {

    public int rob(int[] nums) {

        // if we have only one house . He can rob only one house

        // if we two houses . He can max of the two houses.

        // if three houses . he can rob 3rd and add to 1st house. But if second half alone can have // //more. so have to choose max of both. Max(2nd house , 1st house + 3rd house)

        // 

        int premax = 0;

        int prepremax = 0;

        int maxrob = 0;

        for(int i=0;i<nums.length;i++){

            nums[i] = Math.max(nums[i]+prepremax,premax); // main thing here is to form the base case.

            prepremax = premax;

            premax = nums[i];

            maxrob = Math.max(maxrob,nums[i]);

        }

        return maxrob;

    }

}

Time Complexity : O(n)

Space Complexity : O(1)

LeetCode - Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Java Solution :

class Solution {

    public int maxSubArray(int[] nums) {

        int dp[] = new int[nums.length];

        dp[0] = nums[0];

        for(int i=1;i<nums.length;i++){

            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);

        }

        int maxValue = dp[0];

        for(int i = 1;i < nums.length;i++){

            maxValue = Math.max(maxValue,dp[i]);

        }

        return maxValue;

    }

}

Time Complexity : O(n)

Space Complexity: O(n) because we are using an array of size n.

Second Solution :

class Solution {

    public int maxSubArray(int[] nums) {

        int maxValue = nums[0];

        for(int i=1;i<nums.length;i++){

            nums[i] = Math.max(nums[i-1] + nums[i],nums[i]);

        }

        for(int i = 1;i < nums.length;i++){

            maxValue = Math.max(maxValue,nums[i]);

        }

        return maxValue;

    }

}

Time Complexity : O(n)

Space Complexity : O(1)

Python Posts:

MaxSubArray Python (LeetCode)

LeetCode - Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Java Solution :

class Solution {

    public int maxProfit(int[] prices) {

        int minPrice = Integer.MAX_VALUE;

        int maxProfit = 0;

        

        for(int i =0 ; i < prices.length ; i++){

            if(prices[i] < minPrice)

                minPrice = prices[i];

            else if(prices[i]-minPrice > maxProfit)

                maxProfit = prices[i] - minPrice;

        }

        return maxProfit;

    }

}

Time Complexity : O(n)

Space Complexity : O(1)

Other Solution :

class Solution {

    public int maxProfit(int[] prices) {

        int maxProfit = 0;

        for(int i =0 ; i < prices.length ; i++){

            for(int j = i+1; j < prices.length ; j++){

                maxProfit = Math.max(maxProfit,prices[j]-prices[i]);

            }

        }

        return maxProfit;

    }

}

Time Complexity : O(n*n)

where n is the length of input array length.

Space Complexity : O(1)

LeetCode - Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Java Solution :

class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1 || n == 2)
            return n;
        int previousstep = 2;
        int prepreviousstep = 1;
        for(int i = 3; i <= n ; i++){
            int current = previousstep + prepreviousstep;
            prepreviousstep = previousstep;
            previousstep = current;
        }
        return previousstep;
    }
}

Time Complexity : O(n)

Space Complexity : O(1)

Approach : Dynamic Programming Tabularization.

HTTP Methods , Restful API Methods , URI examples

GET METHOD :

HTTP GET http://oms.com/orders/1
HTTP GET http://oms.com/orders

POST METHOD :

HTTP POST http://oms.com/orders/
HTTP POST http://oms.com/users/1/products

The difference between the POST and PUT APIs can be observed in request URIs. POST requests are made on resource collections, whereas PUT requests are made on an individual resource.

PUT METHOD :
HTTP PUT http://oms.com/orders/1/gg@gmail.com
HTTP PUT http://oms.com/users/2/orders/2

DELETE METHOD :

HTTP DELETE http://oms.com/orders/2
HTTP DELETE http://oms.com/users/3

PATCH METHOD :

PATCH is used to partial update on a  resource not like PUT which is used for entire resource update.

HTTP PATCH http://oms.com/orders/1/users/2/hh@gmail.com

What is the difference between PUT and POST methods in Rest API ?

PUT method is idempotent. Which means it produces same result . How many times you call that mention the result will be same.

Where Post method will produce different result when ever you call that function.

Post method is used to create a new resource.

PUT method is used in general to update a resource .

LeetCode - Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

Example 1:

Input: 1
Output: "A"

Example 2:

Input: 28
Output: "AB"

Example 3:

Input: 701
Output: "ZY"

Java Solution :

class Solution {
    public String convertToTitle(int n) {
        
        StringBuilder sb = new StringBuilder();
        
        while(n > 0){
            n--;
            char ch = (char) (n%26 + 'A');
            n = n/26;
            sb.append(ch);
        }
        sb.reverse();
        return sb.toString();
        
    }
}