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

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