Pascal's Triangle II - LeetCode

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 3
Output: [1,3,3,1]
Java Solution :
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(1);
        if(rowIndex == 0)
            return result;
        for(int i = 1; i <=  rowIndex ; i++){
            for(int j = i-1;j > 0; j--){
                result.set(j,result.get(j-1)+result.get(j));
            }
            result.add(1);
        }
        return result;
    }
}

Pascal's Triangle - LeetCode

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
Java Solution :
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(numRows == 0)
           return result;
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        result.add(row);
        for(int i=1;i<numRows;i++){
            List<Integer> prevRow = new ArrayList<Integer>();
            prevRow = result.get(i-1);
            row = new ArrayList<>();
            row.add(1);
            for(int j=1 ; j < i ; j++){
                row.add(prevRow.get(j-1)+prevRow.get(j));
            }
            row.add(1);
          result.add(row);
        }
        return result;
    }
}
Time Complexity : O(n*n)
Space Complexity : O(n*n)

Data Structures and Algorithms Tutorial


Why Sorting ?

Sorting is  used to order the elements or data in increasing or decreasing order or in lexicographical order.

More than 25% of time spent on sorting in computing .

Use Cases :

1. For searching , sorting is a kind of pre-computation done on data. So that element can be easily found.

2. Sorting is used to find duplicates in a group of elements.

   i.e when you sort all the elements will be in order and duplicate elements will be next to each other and easily be found. (Duplicates will be in consecutive)

3. Matching items in two files . When you sort the two files and matching items can be easily found in single pass.

   i.e This can be implemented using merge sort.

4. Median can be easily when sorted.

    i.e After sorted middle element will be the median.

5. Top K minimum or maximum elements.

6.  Truncated top of items that are relevant to our search.

Ex : Facebook feed , Google search , Gmail search , Twitter feed , Instagram feed , Airbnb homes search , Amazon search bar results.


Main Usage :

1. How to attack new problems .

Algorithm design strategies like Divide and Conquer and Decrease and Conquer.

2.  To analyse algorithms to determine their performance. So that you can choose between two competing solutions of a problem.

Brute Force Design Strategy :

Brute Force is a simplest and straight forward design strategy based up on the problem statement.

Selection Sort :

Selection sort means iterate over the unsorted array and find the minimum element and place it in it's right position.

An algorithm efficiency is determined by it's time and space complexity.

Selection sort Algorithm :

Java Solution :

Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Java Solution : Selection Sort
class Solution {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> sortedList = new ArrayList<>();
        for(int i = 0; i < nums.length;i++){
            int minimumValueIndex = i;
            for(int j=i+1; j < nums.length;j++){
                if(nums[j] < nums[minimumValueIndex]){
                    minimumValueIndex = j;
                }
            }
            if(i != minimumValueIndex){ // To skip this loop when elements at both indexes are equal.
                int temp = nums[i];
                nums[i] = nums[minimumValueIndex];
                nums[minimumValueIndex] = temp;
            }
        }   
        for(int i=0;i < nums.length;i++){
            sortedList.add(new Integer(nums[i]));
        }
        return sortedList;
    }
}
Time Complexity : O(n*n) because two for loops.
Space Complexity : O(n) space for LinkedList
Bubble Sort :
Java Solution : Bubble Sort
class Solution {
    public List<Integer> sortArray(int[] nums) {
        // Bubble Sort
        // In bubble sort we will iterate from right to left and bubble up if we find any right element is less than it's left element and in each iteration minimum element will come to it's position.
        // Bubble sort is a variant of brute force approach.
        List<Integer> sortedList = new ArrayList<>();
        int temp = 0;
        for(int i = 1 ;i < nums.length;i++){
            for(int j = nums.length-1; j > 0 ; j--){
                if(nums[j-1] > nums[j]){
                    temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
        }
        for(int num : nums){
            sortedList.add(new Integer(num));
        }
        return sortedList;
    }
}
Time Complexity : O(n*n) n is no fo iterations . other n for number of swaps.
Space Complexity : O(n)



 






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.

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...