Next greater number with same digits

Given an integer number, find out next greater number formed with same digits.

Approach 1: 
If we carefully look at integer numbers, if all the digits are sorted in ascending order then it's the lowest number you can get with same digits. If we descending sort all the numbers then we will get the greatest number which can be formed with same digits.
So in order to generate the required number start from rightmost digit, check where any of the digits is less than the digit in right, if yes then mark that position.
Now sort all the digits in right from that position, and replace that digit with a greater digit in the sorted list.

The solution below implements this approach.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NextNumberWithSameDigits {
    public static void main(String[] args) {
        int number = 12;

        List integerList = ConvertToArray(number);
        int swapIndex = 1;
        while (swapIndex < integerList.size() && integerList.get(swapIndex-1) <= integerList.get(swapIndex)){
            swapIndex++;
        }

        if (swapIndex == integerList.size()){
            System.out.println("No next greater number can be formed");
            return;
        }

        Integer value = integerList.get(swapIndex);

        List copyList = integerList.subList(0, swapIndex+1);
        Collections.sort(copyList);

        int replaceIndex = 0;
        for (; replaceIndex < copyList.size(); replaceIndex++){
            if (value.equals(copyList.get(replaceIndex))){
                break;
            }
        }

        //If digits are duplicate in the list then we should need next greater digit
        for (; replaceIndex + 1 < copyList.size(); replaceIndex++){
            if (!copyList.get(replaceIndex).equals( copyList.get(replaceIndex+1))){
                Integer temp = copyList.get(replaceIndex+1);
                copyList.remove(replaceIndex+1);
                copyList.add(0, temp);
                break;
            }
        }

        Collections.reverse(copyList);
        Collections.reverse(integerList);

        StringBuilder str = new StringBuilder();
        integerList.forEach(str::append);

        System.out.println("Number : " + number);
        System.out.println("Next   : " + str.toString());

    }

    public static List ConvertToArray(int num){
        List integerList = new ArrayList<>();
        while (num > 0){
            int reminder = num %10;
            num = num/10;
            integerList.add(reminder);
        }
        return integerList;
    }
}

Comments are welcome.

Finding out running Maximum element from stack

You have an empty sequence, and you will be given  queries. Each query is one of these three types:

• 1 num  Push the element x into the stack.
• 2          Delete the element present at the top of the stack.
• 3          Print the maximum element in the stack.

For each query of type 3 return the max element from the current stack.
Input:

10
1 9
1 7
3 
2
1 20
1 26
2
3
1 45
3

 Output: 

9
20
45 

Approach 1:
Use a temp variable to store a maximum element. When the maximum is removed from the stack, iterate through stack and find out next maximum element.

Approach 2:
When we are removing any element from stack and if its max element, then we will have to re-calculate the maximum from existing stack which would be time consuming task. 
We can use the another stack to store the local maximum for stack so far, by adding element in local maximum stack if its greater than current top element.
Only overhead with the maximum stack is when any of the max is removed from the original stack, we should also remove it from maximum stack.
Code below implement this solution.

import java.util.Scanner;
import java.util.Stack;

public class MaxStack {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int queries = scanner.nextInt();

        Stack integerStack = new Stack();
        Stack localMaxStack = new Stack();

        while (queries > 0) {
            int query = scanner.nextInt();
            queries--;
            switch (query) {
                case 1:
                    int value = scanner.nextInt();
                    integerStack.push(value);
                    if (localMaxStack.isEmpty() || value >= localMaxStack.peek())
                        localMaxStack.push(value);
                    break;
                case 2:
                    if (integerStack.isEmpty()) {
                        System.out.println("Invalid Operation !! Stack Empty");
                        System.exit(-1);
                    }
                    value = integerStack.pop();
                    if (!localMaxStack.isEmpty() && value == localMaxStack.peek())
                        localMaxStack.pop();
                    break;
                case 3:
                    if (!localMaxStack.isEmpty()) {
                        System.out.println(localMaxStack.peek());
                    }else {
                        System.out.println("Stack Empty");
                    }
                    break;
                default:
                    System.out.println("Invalid Operation");
                    System.exit(-1);
            }
        }
    }
}

Comments are welcome.

Left shift or Rotating an Array

Given an array and a number, rotate the array to the left by given number positions i.e; shift the array elements to the left.

Example: The array [1, 2, 3, 4, 5] after rotating by 3  gives [ 4, 5, 1, 2, 3].

Approach 1:

Use then temporary array to hold elements to shift at the end. Now shift remaining elements to the front. Append elements in temp array to end.

Approach 2:

Shift one element at a time. This way you will have to move all elements till required rotations are not achieved.

Approach 3:

Reverse elements to be shifted first. Then reverse remaining elements in place then reverse the whole array.

Example: 1, 2, 3, 4, 5 rotate left by 3 then

3, 2, 1, 4 ,5 -> Step1

3, 2, 1, 5, 4 -> Step 2

4, 5, 1, 2, 3 -> Step 3 

Below is the code for this approach.

public class ArrayRotation {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int size = array.length;
        int rotations = 3;

        array = rotate(array, 0, rotations - 1);
        array = rotate(array, rotations, size - 1);
        array = rotate(array, 0, size - 1);

        for (int i = 0; i < size; i++)
            System.out.print(array[i] + " ");

    }

    public static int[] rotate(int[] array, int start, int rotation) {
        for (int i = start; i < rotation; i++, rotation--) {
            int temp = array[i];
            array[i] = array[rotation];
            array[rotation] = temp;
        }
        return array;
    }
}

Comments are welcome.

Surpasser Count of each element in an array

Given an array of distinct integers, for each element of the array count the number of elements to the right that are greater than that element.

A surpasser of an element of an array is a greater element to its right, therefore x[j] is a surpasser of x[i] if i < j and x[i] < x[j].

Example:

input = [6, 5, 4, 7, 2, 8, 0]

output= [2, 2, 2, 1, 1, 0, 0]

Approach 1:

Simplest approach to iterate every time throught the array and find out greater element to it's right. This approach would require O(n^2) complexity and no space complexity.

Approach 2:

We can use O(n)  extra space and solve this efficiently. Priority queue can be used here to store the element in sorted order so that we can check the number of greater element in faster manner. So the complexity will be similar to the time required to push element to priority queue and removing from the same to check for greater element.

Steps:

Start from rear end of array, pick one element each time

Check if queue head is greater than current element 
if yes means all the element in queue are greater than current element.

Save the size of queue as output for specific index of input array

if no then remove element from queue and store it to stack for temporaty storage.
Go to step 1 again



Approach 2 is implemented in solution below.

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class SurpasserCount {
    public static void main(String[] args) {
        int[]  input = {6, 5, 4, 7, 2, 8, 0};
        int[] output = new int[input.length];

        Queue queue = new PriorityQueue();
        Stack stack = new Stack();

        for ( int i = input.length -1; i >= 0; i-- ){
            while (!queue.isEmpty()) {
                if (queue.peek() > input[i]) {
                    output[i] = queue.size();
                    break;
                } else {
                    stack.push(queue.remove());
                }
            }
            if (queue.isEmpty())
                output[i]=0;

            while (!stack.isEmpty()){
                queue.add(stack.pop());
            }

            queue.add(input[i]);
        }

        for (int i: output) {
            System.out.print(i + " ");
        }
    }
}
 

Comments are welcome.
Problem Source 

Check if Substrings are palindrome

Given a string and several queries on substrings of the given input string, check whether the substring is a palindrome or not.

Approach 1:

Simplest approach is to get the substring and check if the substring is palindrome or not. This can be done directly checking each character with its reverse position. 

This way you will have to check palindrome for all the input queries.

Approach 2:

We can find out all the palindrome in the string using dynamic programming in o(n^2) complexity and then use the DP solution return result for each query.   

To find out if string is palindrome we will follow below method:

• String with size 1 is palindrome
• String with size 2 is palindrome if both characters are same
• String with size 3 or more is the palindrome if characters in between are a palindrome.

Solution below implements the approach 2:

import java.util.Scanner;

public class Palindrome {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();

        int queryI = sc.nextInt();
        int queryJ = sc.nextInt();

        int length = str.length();

        boolean[][] dp = new boolean[length][length];

        for (int diff = 0; diff < str.length(); diff++) {
            for (int i = 0, j = diff; j < str.length(); i++, j++) {
                switch (diff) {
                    case 0:
                        dp[i][j] = true;
                        break;
                    case 1:
                        dp[i][j] = str.charAt(i) == str.charAt(j);
                        break;
                    default:
                        dp[i][j] = dp[i + 1][j - 1] && str.charAt(i) == str.charAt(j);
                        break;
                }
            }
        }

        System.out.println("Substring from " + queryI + " to " + queryJ + " is palindrome : "  + dp[queryI][queryJ]);
    }
}

Comments are welcome.