Max distance between same elements using Hashing

Problem Statement:

Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element.

Input:
The first line of input will contain no of test cases T . Then T test cases follow . Each test case contains 2 lines. The first line of each test case contains an integer N denoting the number of elements in the array, the next line contains N space separated integer's.

Output:
For each test case in new line print the Maximum distance between two occurrences of an element

Constraints:
1<=T<=100
1<=N<=1000

Example:
Input
2
6
1 1 2 2 2 1
12
3 2 1 2 1 4 5 8 6 7 4 2
Output
5
10
Explanation
Test case 1:
arr[] = {1, 1, 2, 2, 2, 1}
Max Distance: 5
Distance for 1 is: 5-0 = 5
Distance for 2 is : 4-2 = 2
Max Distance 5
Test case 2:
arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Max Distance 10
maximum distance for 2 is 11-1 = 10
maximum distance for 1 is 4-2 = 2
maximum distance for 4 is 10-5 = 5

Solution:

import java.util.Scanner;
import java.util.*;
class Max_Dis_Between_Same_Element
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t =sc.nextInt();
        while(t>0)
        {
            int n = sc.nextInt();
            int arr[] = new int[n];
            for(int i=0;i<n;i++)
                arr[i] = sc.nextInt();
            MuscleJava g = new MuscleJava();
            System.out.println(g.maxDistance(arr,n));
       
        t--;
        }
    }
}
class MuscleJava
{
    int maxDistance(int arr[], int n)
    {
        int max=0;
        HashMap<Integer,Integer> lastIndex = new HashMap<>();
        HashMap<Integer,Integer> FirstIndex = new HashMap<>();
        for(int i=0; i<n; i++)
        {
            lastIndex.put(arr[i],i);
            if(!FirstIndex.containsKey(arr[i]))
                FirstIndex.put(arr[i],i);
        }
        for(int i=0; i<n; i++)
        {
            int first = FirstIndex.get(arr[i]);
            int last = lastIndex.get(arr[i]);
            if((last - first) > max )
                max = last - first;
        }
        return max;
    }
} 

Minimum indexed character using Hashing

Problem Statement:

Given a string str and another string patt. Find the character in patt that is present at the minimum index in str. If no character of patt is present in str then print ‘$’.
Input:
The first line of input contains an integer T denoting the number of test cases. Then the description of T test cases follow. Each test case contains two strings str and patt respectively.
Output:
Output the character in patt that is present at the minimum index in str. Print "$" (without quotes) if no character of patt is present in str.
User Task:
The task is to complete the function printMinIndexChar() which finds the character in patt that is present at minimum index in str.
Constraints:
1 <= T <= 10⁵
1 <= |str|, |patt| <= 10⁵
Example:
Input:
2
geeksforgeeks
set
adcffaet
onkl
Output:
e
$
Explanation:
Testcase 1: e is the character which is present in given patt "geeksforgeeks" and is first found in str "set".

Solution:

import java.io.*;
import java.util.*;
class GFG 

{
    public static void main (String[] args) throws IOException 

    {
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
       
        while(t-- > 0)

        {
           
            String str = br.readLine();
            String patt = br.readLine();
            PrintString obj = new PrintString();
            System.out.println(obj.printMinIndexChar(str, patt));
           
        }
       
    }
}

class PrintString

{
       public static String printMinIndexChar(String str, String patt)
    {
        HashMap<Character,Integer> h = new HashMap();
        for(int i=0; i<str.length(); i++)
        {
            if(!h.containsKey(str.charAt(i)))
                h.put(str.charAt(i) , i);
        }
        String min = "$";
        int minIndex = 10000;
        for(int i=0; i<patt.length(); i++)
        {
            if(h.containsKey(patt.charAt(i)))
                if(h.get(patt.charAt(i)) < minIndex)
                {
                    minIndex = h.get(patt.charAt(i));
                    min = patt.charAt(i) + "";
                }
        }
        return min;
    }
   
} 

Count pairs with given sum using Hashing

Problem Statement:

Given an array of integers, and an integer  ‘K’ , find the count of pairs of elements in the array whose sum is equal to 'K'.

Input:
First line of the input contains an integer T, denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains 2 space separated integers N and K denoting the size of array and the sum respectively. Second line of each test case contains N space separated integers denoting the elements of the array.

Output:
Print the count of pairs of elements in the array whose sum is equal to the K.

Constraints:
1<=T<=50
1<=N<=50
1<=K<=50
1<=A[i]<=100

Example:
Input
2
4 6
1  5  7 1
4 2
1 1 1 1
Output
2
6

Solution:

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

class MuscleJava
{
    public static void main (String[] args)
    {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while(t-->0)
        {
            int n = s.nextInt();
            int k = s.nextInt();
            int arr[] = new int[n];
            int count = 0;
            HashMap<Integer,Integer> h = new HashMap();
            for(int i=0; i<n; i++)
            {
                arr[i] = s.nextInt();
                int temp = arr[i];
                if(!h.containsKey(arr[i]))
                    h.put(temp,0);
                h.put(temp, h.get(temp)+1 );
            }
            for(int i=0; i<n; i++)
            {
                if(h.get(k-arr[i]) != null)
                {
                    count += h.get(Math.abs(k-arr[i]));
                }
               
                if(arr[i]+arr[i] == k)
                    count--;
            }
            System.out.println(count/2);
        }
    }
} 

Get minimum element from stack in O(1) time

Problem Statement:

You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.
Input:
The first line of the input contains an integer 'T' denoting the number of test cases. Then T test cases follow. First line of each test case contains an integer Q denoting the number of queries.
A Query Q may be of 3 Types:
    1. 1 x (a query of this type means  pushing 'x' into the stack)
    2. 2 (a query of this type means to pop element from stack and print the poped element)
    3. 3 (a query of this type means to print the minimum element from the stack)
The second line of each test case contains Q queries seperated by space.
Output:
The output for each test case will  be space separated integers having -1 if the stack is empty else the element poped out  or min element from the stack.
User Task:
You are required to complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer poped out from the stack and getMin() which returns the min element from the stack.
Constraints:
1 <= T <= 100
1 <= Q <= 100
1 <= x <= 100
Example:
Input:
1
6
1 2 1 3 2 3 1 1 3   
Output:
3 2 1
Explanation:
Testcase 1:
In the first test case for query
1 2  the stack will be {2}
1 3  the stack will be {2 3}
2 poped element will be 3 the stack will be {2}
3 min element will be 2
1 1 the stack will be {2 1}
3 min element will be 1

Solution: 

import java.util.*;
class Get_Min_From_Stack
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T>0)
        {
            int q = sc.nextInt();
            MuscleJava g = new MuscleJava();
            while(q>0)
            {
                int qt = sc.nextInt();
               
                if(qt == 1)
                {
                    int att = sc.nextInt();
                    g.push(att);
                }
                else if(qt == 2)
                {
                    System.out.print(g.pop()+" ");
                }
                else if(qt == 3)
                {
                    System.out.print(g.getMin()+" ");
                }
           
            q--;
            }
            System.out.println();
        T--;
        }
       
    }
}

class MuscleJava
{
    int minEle; 
    Stack<Integer> s = new Stack();
    // System.out.println("Statck " + s);
    /*returns min element from stack*/
    int getMin()
    {
        if(s.isEmpty() )
            return -1;
        return minEle;
    }
   
    /*returns poped element from stack*/
    int pop()
    {
        if(s.size() == 0 )
            return -1;
        else if(s.peek() >= minEle)
            return s.pop();
        else
        {
            minEle = 2*minEle - s.pop();
            return (minEle);
        }
    }
    /*push element x into the stack*/
    void push(int x)
    {
        if( s.isEmpty() )
        {
            s.push(x);
            minEle = x;
        }
        else if(x < minEle)
        {
            int prevMin = minEle;
            minEle = x;
            s.push(((2*minEle) - prevMin));
        }
        else
            s.push(x);
    }   
}

Sort a stack

    Problem Statement:

Given a stack, the task is to sort it such that the top of the stack has the greatest element.

Input:
The first line of input will contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer N denoting the size of the stack. Then in the next line are N space separated values which are pushed to the the stack.

Output:
For each test case output will be the popped elements from the sorted stack.

Constraints:
1<=T<=100
1<=N<=100

Example(To be used only for expected output):
Input:
2
3
3 2 1
5
11 2 32 3 41

Output:
3 2 1
41 32 11 3 2

Explanation:
For first test case stack will be
1
2
3
After sorting
3
2
1

When elements  popped : 3 2 1

Solution:

 

import java.util.Scanner;
import java.util.Stack;
class SortedStack{
    public static void main(String[] args)

   {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)

       {
            Stack<Integer> s=new Stack<>();
            int n=sc.nextInt();
            while(n-->0)
            s.push(sc.nextInt());
            MuscleJava g=new MuscleJava();
            Stack<Integer> a=g.sort(s);
            while(!a.empty()){
                System.out.print(a.peek()+" ");
                a.pop();
            }
            System.out.println();
        }
    }
}

class MuscleJava
{
    public Stack<Integer> sort(Stack<Integer> s)
    {
        Stack<Integer> t = new Stack<Integer>();
        while(s.size() > 0)
        {
            if(t.empty() || t.peek() < s.peek() )
                t.push(s.pop());
            else
            {
                int temp = s.pop();
                while(t.size() > 0 && t.peek() >= temp)
                {
                    s.push(t.pop());
                }
                t.push(temp);
            }
        }
        return t;
    }
} 

Reverse a string using Stack

Problem Statement:

An string of words is given, the task is to reverse the string using stack.
Input Format:
The first line of input will contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains a string s of words without spaces.
Output Format:
For each test case ,print the reverse of the string in new line. 
Your Task:
Since this is a function problem, you don't need to take any input. Just complete the provided function.
Constraints:
1 <= T <= 100
1 <= length of the string <= 100
Example:
Input:
2
MuscleJava
CodeJavaMuscle
Output:
avaJelcsuM
elcsuMavaJedoC

Solution:

public class MuscleJava
{
    public void reverse(String str)
    {
       Stack<Character> st = new Stack();
       for(int i=0; i<str.length(); i++)
       {
           st.push(str.charAt(i));
       }
       while(st.size() > 0 )
        {
            System.out.print(st.pop());
        }
        System.out.println();
    }

    public static void main (String[] args)
    {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
         for(int k=0;k < t; k++)
         {
             String in = s.next();

             reverse(in);
         }
    }
} 

Nearest smaller numbers on left side in an array

  Problem Statement:

Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.If no small element present on the left print -1.
Input:
The first line of input contains T test cases. 
The first line of each test case contains the number of elements in the array.
The second line of each test case contains the elements of the array.
Output:
Print the n elements.
Constraints:
1<=T<=100
1<=N<=100
0<=A[i]<10000
Example:
Input:
2
3
1 6 2
6
1 5 0 3 4 5
Output:
-1 1 1
-1 1 -1 0 3 4

Solution:

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

class MuscleJava
{
    public static void print(int arr[], int n)
    {
        Stack st = new Stack();
        for(int i=0; i         {
            // System.out.println("\n" + i);
            while(!st.empty() && arr[i] <= st.peek() )
            {
                st.pop();
            }
            if(st.empty())
                System.out.print("-1 ");
            else
                System.out.print(st.peek() + " ");
            st.push(arr[i]);
        }
    }
    public static void main (String[] args)
    {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
         for(int k=0;k < t; k++)
         {
             int n = s.nextInt();
             int arr[] = new int[n];
             for(int i=0; i              {
                 arr[i] = s.nextInt();
             }
             print(arr,n);
             System.out.println();
         }
    }
}