The Coding Shala

Home >> LeetCode >> Remove Outermost Parentheses  In this post, we will learn how to solve LeetCode's Remove Outermost Parentheses problem and will implement its solution in Java. Remove Outermost Parentheses Problem A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.  For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings. Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S. Example 1: Input: "(()())(())" Output: "()()()" Explanation:  The input string is "(()())(())", with primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()" = "()()()". Example 2: Input: "(()()...

Home >> Data Structure >> Implement queue using linked list  In this post, we will learn how to implement Queue using Linked List and will write a Java Program for the same. Implement Queue using Linked List We will implement Queue using Linked List. The basic operation of the queue like push/offer and remove/poll method will implement here. Java Program:  class QueueNode { int data ; QueueNode next ; QueueNode ( int a ) { data = a ; next = null ; } } class MyQueue { QueueNode front , rear ; // This function should add an item at // rear void push ( int a ) { QueueNode newNode = new QueueNode ( a ); if ( front == null || rear == null ) { front = newNode ; rear = front ; } else { rear . next = newNode ; rear = rear . next ; } } // This function should remove front // item from queue and should re...

Home >> Data Structures >> Implement Queue Using Array  In this post, we will learn how to Implement Queue Using Array and will write a Java program for the same. Implement Queue Using Array We will write a simple Java Program to implement queue using the array, Only Push and Pop method we will implement here. Java Program:  class MyQueue { int front , rear ; int arr [] = new int [ 100005 ]; MyQueue () { front = 0 ; rear = 0 ; } /* The method push to push element into the queue */ void push ( int x ) { arr [ rear ] = x ; rear ++; } /* The method pop which return the element poped out of the queue*/ int pop () { if ( front == rear ) return - 1 ; int res = arr [ front ]; front ++; return res ; } } Other Posts You May Like Queue Data Structure Circular Queue Data Structure Stack Data Structure Implement Stack Using Array Implem...

Home >> LeetCode >> Number of Recent Calls  In this post, we will learn how to solve LeetCode's Number of Recent Calls Problem and will implement its solution in Java. Number of Recent Calls Problem You have a RecentCounter class that counts the number of recent requests within a certain time frame. Implement the RecentCounter class: RecentCounter() Initializes the counter with zero recent requests. int ping(int t) Adds a new request at time t, where t represents some time in milliseconds and returns the number of requests that have happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t]. It is guaranteed that every call to ping uses a strictly larger value of t than the previous call. Example 1: Input: ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] Output: [null, 1, ...

Home >> Data Structures >> Implement Stack using Linked List  In this post, we will learn how to Implement Stack Using Linked List and will write a Java Program for the same. Implement Stack using Linked List We will implement Stack operations using LinkedList. If we implement using a linked list then the stack can grow and shrink dynamically but it requires extra memory because of pointers involvement. Java Program:  class MyStack { Node root ; //linked list node class Node { int data ; Node next ; Node ( int data ) { this . data = data ; } } boolean isEmpty () { return root == null ; } void push ( int x ) { Node newNode = new Node ( x ); //if stack is empty //make this as root node if ( root == null ) { root = newNode ; } else { ...

Home >> Data Structures >> Implement Stack Using Array  In this post, we will learn how to Implement Stack Using Array and will write a Java program for the same. Implement Stack Using Array We will implement Stack's operations using an array. If we use an array then it is easy to implement but the size limit is there. Java Program:  class MyStack { static final int MAX = 1000 ; int top ; int a []; boolean isEmpty () { return ( top < 0 ); } MyStack () { top = - 1 ; a = new int [ MAX ]; } void push ( int x ) { if ( top >= ( MAX - 1 )) { //stack overflow //return false or print error } else { a [++ top ] = x ; } } int pop () { if ( top < 0 ) { //stack underflow return - 1 ; } e...

Home >> Java Program >> Swap Two Numbers using XOR  In this post, we will learn how to Swap Two Numbers using XOR and will write a Java Program for the same. Java Program to Swap Two Numbers using XOR Swap two numbers without using an additional variable. Example: Input: a = 10;           b = 20; Output: a = 20;              b = 10; We can use XOR to swap the numbers. Java Program:  public class SwapTwoNumbers { public static void main ( String [] args ) { int a = 10 ; int b = 20 ; System . out . println ( "Before swap" ); System . out . println ( "a: " + a ); System . out . println ( "b: " + b ); //swap using xor a = a ^ b ; b = a ^ b ; a = a ^ b ; System . out . println ( "After swap" ); System . out . println ( "a: " + a ); System . out . println ( "b: " + b ); } } Output:  Before swap a: 10 b: 20 Af...

Home >> LeetCode >> Integer Replacement  In this post, we will learn how to solve LeetCode's Integer Replacement Problem and will implement its solution in Java. Integer Replacement Problem Given a positive integer n, you can apply one of the following operations: If n is even, replace n with n / 2. If n is odd, replace n with either n + 1 or n - 1. Return the minimum number of operations needed for n to become 1. Example 1: Input: n = 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 Example 2: Input: n = 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 Practice this problem on LeetCode . LeetCode - Integer Replacement Java Solution Approach 1 Using Bit Manipulation. If n is even then the operation is fixed. If n is odd then we have two operations +1 or -1, so for this let's check the binary of the number. We need to check only the second bit of the number. (from right side) Case 1. If the second bit is 1, t...