Snippets Collections
// Iterative Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int lastOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == n - 1 || arr[mid + 1] != arr[mid])
					return mid;

				else
					low = mid + 1;
			}

		}

		return -1;
	}
	
	public static void main(String args[]) 
	{
	    int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;
	    
	    int x = 10;
	    
	    System.out.println(lastOcc(arr, n, x));   // OUTPUT : 4
    } 
    
}
 
 
 
 
 
 
// Recursive Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int lastOcc(int arr[], int low, int high, int x, int n)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(x > arr[mid])
			return lastOcc(arr, mid + 1, high, x, n);

		else if(x < arr[mid])
			return lastOcc(arr, low, mid - 1, x, n);

		else
		{
			if(mid == n - 1 || arr[mid + 1] != arr[mid])
				return mid;

			else
				return lastOcc(arr, mid + 1, high, x, n);
		}
	}
	
	public static void main(String args[]) 
	{
	    int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;
	    
	    int x = 10;
	    
	    System.out.println(lastOcc(arr, 0, n - 1, x, n));   // OUTPUT : 4
    } 

}
// Efficient Code (Iterative)

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

class GFG 
{ 
	static int firstOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == 0 || arr[mid - 1] != arr[mid])
					return mid;

				else
					high = mid - 1;
			}

		}
		return -1;
	}

	public static void main(String args[]) 
    {
        int arr[] = {5, 10, 10, 10, 20}, n = 5;

		int x = 10;

        System.out.println(firstOcc(arr, n, x));   // OUTPUT : 1
    } 
}






// Efficient Code (Recursive)

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

class GFG 
{ 
	static int firstOcc(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(x > arr[mid])
			return firstOcc(arr, mid + 1, high, x);

		else if(x < arr[mid])
			return firstOcc(arr, low, mid - 1, x);

		else
		{
			if(mid == 0 || arr[mid - 1] != arr[mid])
				return mid;

			else
				return firstOcc(arr, low, mid - 1, x);
		}
	}

	public static void main(String args[]) 
    {
        int arr[] = {5, 10, 10, 15, 20, 20, 20}, n = 7;

		int x = 20;
		
		System.out.println(firstOcc(arr, 0, n - 1, x));   // OUTPUT : 4
    } 
}






// Naive Code

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

class GFG 
{ 
	static int firstOccurrence(int arr[], int n, int x)
	{
		for(int i = 0; i < n; i++)
			if(arr[i] == x)
				return i;

		return -1;
	}

	public static void main(String args[]) 
    {
        int arr[] = {5, 10, 10, 15, 15}, n = 5;

		int x = 15;
    
        System.out.println(firstOccurrence(arr, n, x));   // OUTPUT : 3
    } 
}
import java.util.*;
import java.io.*;
  
class GFG { 
       
    static void patSearchinng(String txt,String pat)
    {
        int m=pat.length();
        int n=txt.length();
        for(int i=0;i<=(n-m); )
        {
            int j;
            for(j=0;j<m;j++)
                if(pat.charAt(j)!=txt.charAt(i+j))
                    break;
            
            if(j==m)
                System.out.print(i+" ");
            if(j==0)
                i++;
            else
                i=(i+j);
        }
    }
  
    public static void main(String args[]) 
    {   String txt = "ABCABCD";String pat="ABCD";
        System.out.print("All index numbers where pattern found: ");
        patSearchinng(txt,pat);  
    } 
} 
import java.util.*;
import java.io.*;
  
class GFG { 
       
    static void patSearchinng(String txt,String pat)
    {
        int m=pat.length();
        int n=txt.length();
        for(int i=0;i<=(n-m);i++){
      	    int j;
            for(j=0;j<m;j++)
                if(pat.charAt(j)!=txt.charAt(i+j))
              	    break;
            
        if(j==m)
            System.out.print(i+" ");
        }
    }
  
    public static void main(String args[]) 
    {   String txt = "ABCABCD";String pat="ABCD";
        System.out.print("All index numbers where pattern found: ");
        patSearchinng(txt,pat);  
    } 
} 
// One Traversal
// Efficient Approach-1 : Time Complexity : O(n)
 
    static final int CHAR=256;
    static int nonRep(String str) 
    {
        int[] fI=new int[CHAR];
        Arrays.fill(fI,-1);
    
        for(int i=0;i<str.length();i++){
            if(fI[str.charAt(i)]==-1)
            fI[str.charAt(i)]=i;
            else
            fI[str.charAt(i)]=-2;
        }
        int res=Integer.MAX_VALUE;
        for(int i=0;i<CHAR;i++){
            if(fI[i]>=0)res=Math.min(res,fI[i]);
        }
        return (res==Integer.MAX_VALUE)?-1:res;
    }
 
 
// Two Traversal
// Better Approach : Time Complexity : O(n) 
 
    static final int CHAR=256;
    static int nonRep(String str) 
    {
        int[] count=new int[CHAR];
        for(int i=0;i<str.length();i++){
            count[str.charAt(i)]++;
        }
        for(int i=0;i<str.length();i++){
            if(count[str.charAt(i)]==1)return i;
        }
        return -1;
    } 
 
 
// Naive Code : Time Complexity : O(n^2)
 
    static int nonRep(String str) 
    {
        for(int i=0;i<str.length();i++){
            boolean flag=false;
            for(int j=0;j<str.length();j++){
                if(i!=j&&str.charAt(i)==str.charAt(j)){
                    flag=true;
                    break;
                }
            }
            if(flag==false)return i;
        }
        return -1;
    }
// Efficient Approach-2 : Time & Space similar to previous method

    static final int CHAR=256;
    static int leftMost(String str) 
    {
        boolean[] visited=new boolean[CHAR];
        int res=-1;
        for(int i=str.length()-1;i>=0;i--){
            if(visited[str.charAt(i)])
            res=i;
            else
            visited[str.charAt(i)]=true;
        }
        
        return res;
    } 



// One Traversal
// Efficient Approach-1 : Time Complexity : O(n + CHAR), Auxiliary Space : O(CHAR)

    static final int CHAR=256;
    static int leftMost(String str) 
    {
        int[] fIndex=new int[CHAR];
        Arrays.fill(fIndex,-1);
        int res=Integer.MAX_VALUE;
        for(int i=0;i<str.length();i++){
            int fi=fIndex[str.charAt(i)];
            if(fi==-1)
            fIndex[str.charAt(i)]=i;
            else
            res=Math.min(res,fi);
        }
        
        return (res==Integer.MAX_VALUE)?-1:res;
    } 



// Better Approach : Time Complexity : O(n) but requires two loops for input string 

    static final int CHAR=256;
    static int leftMost(String str) 
    {
        int[] count=new int[CHAR];
        for(int i=0;i<str.length();i++){
            count[str.charAt(i)]++;
        }
        for(int i=0;i<str.length();i++){
            if(count[str.charAt(i)]>1)return i;
        }
        return -1;
    }


// Naive Code : Time Complexity : O(n^2)

    static int leftMost(String str) 
    {
        for(int i=0;i<str.length();i++){
            for(int j=i+1;j<str.length();j++){
                if(str.charAt(i)==str.charAt(j))return i;
            }
        }
        return -1;
    }

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension