LeetCode Medium: Product of Array Except Self

 Problem Name: Product of Array Except Self

Problem Description: https://leetcode.com/problems/product-of-array-except-self/

Problem Approach used: It's an easy problem to solve, just keep in mind your Indeterminate Numbers lesson of High School to solve it.

Time Complexity:  O(n) worst-case time complexity and O(1) auxiliary space complexity.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution { public int[] productExceptSelf(int[] nums) { long prodArr = 1; long non0ProdArr = 1; int countZeroes = 0; for (int i=0; i<nums.length; i++) { if (nums[i] == 0) countZeroes++; if (nums[i] != 0) non0ProdArr *= nums[i]; prodArr *= nums[i]; } int[] answer = new int[nums.length]; if (countZeroes > 1) { Arrays.fill(answer, 0); return answer; } for (int i=0; i<nums.length; i++) { if (nums[i] == 0 && countZeroes == 1) { countZeroes--; answer[i] = (int)non0ProdArr; } else { answer[i] = (int)(prodArr / (long)nums[i]); } } return answer; } }

Until Next time, Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

Leetcode Medium: Set Matrix Zeroes

 Problem Name: Set Matrix Zeroes

Problem Description: https://leetcode.com/problems/set-matrix-zeroes/

Problem Approach used: Its a trick problem to solve it in constant space. We've used the same, using HashSets in the below solution.

Time Complexity:  O(m*n) worst-case time complexity and O(1) auxiliary space complexity.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

// In 1 line of thought, constant space solution is ideally not possible as all possible int values can be part of the matrix, but if we can assume some sentinel value out of these (like Integer.MIN_VALUE in our case) for marking original zeroes, a solution follows. // * Also we can use a trick to solve ths problem: marking 1st(top and left) elements of the row and column respetively, to 0. class Solution { Set<Integer> toZeroRows = new HashSet<>(), toZeroColumns = new HashSet<>(); public void setZeroes(int[][] matrix) { for (int row=0; row<matrix.length; row++) { for (int column=0; column<matrix[0].length; column++) { if (matrix[row][column] == 0) { toZeroRows.add(row); toZeroColumns.add(column); } } } // Print initial matrix printMatrix(matrix); for (int row=0; row<matrix.length; row++) { if (toZeroRows.contains(row)) { for(int columnIndex=0; columnIndex<matrix[0].length; columnIndex++) { matrix[row][columnIndex] = 0; } } } printMatrix(matrix); for (int column=0; column<matrix[0].length; column++) { if (toZeroColumns.contains(column)) for(int rowIndex=0; rowIndex<matrix.length; rowIndex++) { matrix[rowIndex][column] = 0; } } printMatrix(matrix); } public void printMatrix(int [][] matrix) { for (int row = 0; row<matrix.length; row++) { for (int column = 0; column<matrix[0].length; column++) { System.out.print(" " + matrix[row][column]); } System.out.println(); } } }

Happy Coding!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

 

Leetcode Problem: Climbing Stairs

 Problem of Today: Climbing Stairs

Problem description: https://leetcode.com/problems/climbing-stairs/

Solution Approach: Memoization

Solution: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { private int memo[]; // Bottom-up public int climbStairs(int n) { memo = new int[n+1]; for (int i=0; i<=n; i++) { memo[n] = -1; } memo[0] = 1; memo[1] = 1; for (int i=2; i<=n; i++) { memo[i] = memo[i-1] + memo[i-2]; } return memo[n]; } }

Happy Coding!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

 

LeetCode Medium: Generate Parentheses

Dear followers,

Tonight, I came across a nice problem for post-dinner exercise, about generating all possible valid parentheses sequences given the number of brackets to use in total.

PROBLEM LINK: https://leetcode.com/problems/generate-parentheses/

PROBLEM SOLVING APPROACH: Recursion (using Choice Diagram and Decision tree)

TIME-COMPLEXITY: O(2^n) in the worst case but the input n is given to be max 8, so very much doable :)

Here's a sample Java solution for your reference:

class Solution {
    public List<String> generateParenthesis(int n) {
        ArrayList<String> generatedParentheses = new ArrayList<>();
        genParenthesesRecur(n, n, "", generatedParentheses);
        return generatedParentheses;
    }
    
    private void genParenthesesRecur (int remOpenBrackets, int remClosingBrackets, String outputFromCaller, List<String> generatedParentheses) {
        // Base Cases
        if (remOpenBrackets < 0 || remClosingBrackets < 0)
            return;
        
        if (remClosingBrackets < remOpenBrackets) {
            return;
        }
        
        if (remOpenBrackets == 0 && remClosingBrackets == 0) {
           generatedParentheses.add(outputFromCaller);
        }
        
        // Recursive Case
        String opUsingAnOpeningBracket = outputFromCaller + "(";
        genParenthesesRecur(remOpenBrackets-1, remClosingBrackets, opUsingAnOpeningBracket, generatedParentheses);
        if (remClosingBrackets > remOpenBrackets) {
            String opUsingAClosingBracket = outputFromCaller + ")";
            genParenthesesRecur(remOpenBrackets, remClosingBrackets-1, opUsingAClosingBracket, generatedParentheses);
        }
    }
}

Thanks for Reading!

Happy Programming!!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

Leetcode Easy: Longest Common Prefix

Tea-time snacking!

PROBLEM: https://leetcode.com/problems/longest-common-prefix/

TIME-COMPLEXITY: O(n*m) where n is the number of strings in input and m is the length of longest common prefix.

Sample Java Solution for tea-time snacking:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1)
            return strs[0];
        
        int minLen = Integer.MAX_VALUE;
        for (int i=0; i<strs.length; i++) {
            minLen = Math.min(minLen, strs[i].length());
        }
        int lastPastIdx = minLen;
        outer:
        for (int i=0; i<minLen; i++) {
            char ch = strs[0].charAt(i);
            for (int str=0; str<strs.length; str++) {
                if (strs[str].charAt(i) != ch) {
                    lastPastIdx = i;
                    break outer;
                }
            }
        }
        return strs[0].substring(0, lastPastIdx);
    }
}

Enjoy and Happy Coding!!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

LeetCode Medium Trick Problem: Longest Consecutive Sequence

Came across this problem on Leetcode, which requires one to focus on optimization.

PROBLEM LINK: https://leetcode.com/problems/longest-consecutive-sequence

TIME COMPLEXITY: O(n) at worst case where n is the number of elements in the input array (precisely the constant factor for n is 2)

APPROACH: The most naive approach to solve this problem would have been to sort the input array using comparison sort in O(n lg n) worst case time complexity and then in single pass find the length of the consecutive sequences in the same, resulting in overall worst case time complexity on O(n lg n).

But, if we notice carefully, we can make use of a trick to solve the problem in O(n) worst case time complexity. The trick makes a space trade off of O(n) and makes use of a HashSet to store the values to quickly check if any number exists in the input array. Then, it checks for all values in input, if it is the start of a consecutive sequence by checking presence of 1 lesser value than that on the number line, in the number Set. If any start-of-consecutive-range is found in the array elements, the length of the range is found by consecutively checking all the numbers in the increasing order on the number line consecutively.

In each such iteration of the numbers in input array, the length of the max-range is updated and the largest value is returned at the end of all iterations.

Here's a sample code for the same:

class Solution {
    
    public int longestConsecutive(int[] nums) {
        Set numberSet = new HashSet ();
        
        // Add numbers to Set while updating length of the longest consecutive elements sequence
        int maxLLCES = 0, currLLCES = 0;
        for (int i=0; i<nums.length; i++) {
            numberSet.add (nums[i]);
        }
        
        for (int i=0; i<nums.length; i++) {
            if (!numberSet.contains(nums[i]-1)) {
                // nums[i] is not a start of a consecutive sequence
                currLLCES = 1;
                int checkNum = nums[i]+1;
                while(numberSet.contains(checkNum)) {
                    currLLCES++;
                    checkNum++;
                }
                maxLLCES = Math.max(maxLLCES, currLLCES);
                // System.out.println("Updated maxLLCES:" + maxLLCES);
            }
        }
        return maxLLCES;
    }
}

Do share your thoughts and feel free to talk about the alternatives/optimisations you feel can be done in the comment section!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

 

Recursion Series: Deleting the middle element from a stack

This post marks the start point of the much awaited recursion series on Let'sCode_ =) 

We start it with a GeeksForGeeks problem : https://www.geeksforgeeks.org/delete-middle-element-stack/

Position of Middle element of all elements from top of stack (1 based):

stack.size()/2 + 1

Now, to build an effective solution we can use:

Methodology: Recursion

Time Complexity: O(n) where n is the number of elements in the stack

Space Complexity: O(n) considering the accumulation of constant space in each level of the recursive stack. O(1) if we dis-consider the stack space accumulation.

Here is one such solution:

<-- --todeletepos="" base="" case="" deletemidrecur="" int="" nteger="" printstack="" private="" return="" stack.pop="" stack.push="" stack="" static="" tack="" top="" void="">/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;

class GFG {
	public static void main (String[] args) {
		System.out.println("GfG!");
		Stack<Integer> stack = new Stack<>();
		
		stack.push(6);
		stack.push(5);
		stack.push(4);
		stack.push(3);
		stack.push(2);
		stack.push(1);
		deleteMid(stack);
		
	}
	
	private static void deleteMid(Stack<Integer> stack) {
	    if (stack == null)
	        return;
	    if (stack.isEmpty())
	        return;
	        
	    int mid = stack.size()/2+1;
	    deleteMidRecur(stack, mid);
	    printStack(stack);
	}
	
	private static void deleteMidRecur (Stack<Integer> stack, int toDeletePos) {
	    if (toDeletePos == 1) {
	        // delete this element <-- base case
	        stack.pop();
	        return;
	    }
	    
	    int top = stack.pop();
	    deleteMidRecur(stack, --toDeletePos);
	    stack.push(top);
	}
	
	private static void printStack (Stack<Integer> stack) {
	    while (!stack.isEmpty()) {
	        System.out.println(stack.pop());
	    }
	}
}

IMO, such are the most efficient solutions to this problem. So share your thoughts and let me know your point of views.

Happy Coding!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

 https://www.facebook.com/theAlgorithmicCoder