Basic Maths

Basic Recursion

Video 1

Problem 1 Answer

Problem

class Solution
{
    
  public void printNos(int N)
    {
        //Your code 
        if(N==0) return;
        printNos(N-1);
        System.out.print(N+" ");
    }
}

Video 2

Problem

Problem 2 Answer

class Solution {

    void printGfg(int N) {
        for(int i = 0;i<N;i++){
            System.out.print("GFG"+" ");
        }
        
    }
}

Video 3

Problem 3 answer

Problem

class Solution {

    void printNos(int N) {
        // code here
        if(N ==0){
            return;
        }
        printNos(N -1);
        System.out.print(N+" ");
        
    }
}

Video 4

Problem 4

Problem

Solution

class Solution {

    void printNos(int N) {
        // code here
        if(N ==0){
            return;
        }
        System.out.print(N+" ");
        printNos(N -1);   
    }
}

Video 5

Problem 5

Problem

Solution

class Solution {
    long sumOfSeries(long n) {
        // code here
        if(n == 0){
            return 0;
        }
        return (long) Math.pow(n,3) + sumOfSeries(n-1);
    }
}

Video 5

Problem 5

Problem

Solution

class Solution {
    static ArrayList<Long> factorialNumbers(long n) {
        // code here
            
            ArrayList<Long> list = new ArrayList<>();
            long fact = 1;
            for(long i = 1;i<=n;i++){
                fact = fact * i;
                if(fact<=n){
                    list.add(fact);
                }
                else {
                    break;
                }
            }
            return list;
            
    }
}

Video 6

Problem 6

1.Using an extra array

Solution

public class Main{
    
    public static void printarray(int ans[],int size){
        System.out.println("Array:");
        for(int i = 0;i<size;i++){
            System.out.print(ans[i]+" ");
        }
    } 
    
    public static void reversearr(int arr[],int size){
        int ans[] = new int[size];{
            for(int i = size - 1;i>=0;i--){
                ans[size - i - 1] = arr[i];
            }
            printarray(ans,size);
        }  
    }
    public static void main (String[] args) {
        int arr[] = {2,3,4,5,6};
        int n = 5;
        reversearr(arr,n);
        
    }
}

2.recursive Method

Solution

public class Main{
    public static void main (String[] args) {
        int arr[] = {1,2,3,4,6,7};
        int n = 5;
        revarrusingrec(arr,0,n - 1);
        printarray(arr,n);
    }
    // reverse array using recursion method

    public static void revarrusingrec(int arr[],int startindex,int endindex){
        if(startindex<endindex){
            // use swap method
            int temporary = arr[startindex];
            arr[startindex] = arr[endindex];
            arr[endindex] = temporary;
            revarrusingrec(arr,startindex + 1,endindex - 1);
        }
    }
    
    // print it
    public static void printarray(int arr[],int size){
        System.out.println("Reverse Array:");
        for(int i = 0;i<size;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

Video 7

Problem

Solution

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase().replaceAll("[^A-Za-z0-9]","");
        int fwd = 0;
        int bwd= s.length()-1;
        while(fwd<=bwd)
        {
            if(s.charAt(fwd) != s.charAt(bwd))
            {
                return false;
            }
            fwd = fwd + 1;
            bwd = bwd - 1;
        }
        return true;
    }
}

Video 8

Problem

Solution

class Solution {
    public int fib(int n) {
        int sum = 0;
        int sum1 = 1;
        for(int i = 0;i<n;i++){
            int sum2 = sum1 + sum;
            sum = sum1;
            sum1 = sum2; 
        }
        return sum;
    }
}

Bit Manipulation

Power Of 4

Problem

Algorithm: Brian's Kernighans

Solution

class Solution {
    public boolean isPowerOfFour(int n) 
    {
        if(n==1){
            return true;
        }
        else if(n>1){
            boolean containssinglebit = (n &(n-1))==0;
            boolean fourorsixinzerobit = (n%10==4 || n%10==6);
            return containssinglebit && fourorsixinzerobit;
        }
        else{
            return false;
        }
    }
}

Power Of 3

Problem

Solution

class Solution {
    public boolean isPowerOfThree(int n) {
    if( n < 1) return false;
    while(n % 3 == 0){
        n = n / 3;
        }
    return n == 1;

    }
}

Single Number

Problem

Solution

class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        int value = 0;
        for(int i = 0;i<len;i++){
            value = value^nums[i];
        }
        return value;
    }
}
			       

Time complexity: O(N) Space Complexity:O(1)

Sorting

Selection Sort

Problem

Solution

import java.util.*;
public class index{
          public static void main(String[] args) {
               Scanner S = new Scanner(System.in);
                int n = 5;
                int arr[]  = new int[n];
                for(int i = 0;i<arr.length;i++)
                {
                    arr[i] = S.nextInt();
                }
                selection_sort(arr,n);
                for(int i = 0;i<arr.length;i++){
                    System.out.println(arr[i]+" ");
                }
          S.close();
          }

          public static void selection_sort(int arr[],int n)
          {
                    // int i,j,min_index,temp;
                    for(int i = 0;i<=n-1;i++){
                              int min_index = i;
                              for (int j = i+1;j<n;j++) {
                                       if (arr[j]<arr[min_index]) 
                                       {
                                        min_index = j;
                                       } 
                              }
                     int temp = arr[min_index];
                     arr[min_index] = arr[i];
                     arr[i] = temp;         
                    }
          }
}

Simple solution Using Sort Method

class solution
{
	int select(int arr[], int n)
	{
        // code here such that selectionSort() sorts arr[]
        return arr[n];
	}
	
	void selectionSort(int arr[], int n)
	{
	    //code here
	    Arrays.sort(arr);
	    for(int i = 0;i<n;i++){
	        select(arr,i);
	    }
	}
}

Time Complexity for Selection Sort Is O(n2)

Bubble Sort

Problem

Solution

import java.util.*;
class solution
{
    public static void main(String args[])
    {
        Scanner S = new Scanner(System.in);
        int size = S.nextInt();
        int arr[] = new int[size];
        for(int i = 0;i<size;i++){
            arr[i] = S.nextInt();
        }
        bubblesort(arr,size);
        for(int j = 0;j<arr.length;j++)
        {
        System.out.print(arr[j] +" ");
        }
    }
        static void bubblesort(int arr[],int n){
        for(int i = n - 1;i>=1;i--)
        {
            int didswap = 0;
            for(int j = 0;j<=i - 1;j++)
            {
                if(arr[j]>arr[j+ 1]){
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                didswap = 1;
                }
            }
            if(didswap == 0){
            break;
            }

        }     

    }

}

Bubble Sort - Time Complexity: O(n)

Simplest Solution using Sort method

class solution
{
	int bubble(int arr[], int n)
	{
        // code here such that bubbleSort() sorts arr[]
        return arr[n];
	}
	
	void bubbleSort(int arr[], int n)
	{
	    //code here
	    Arrays.sort(arr);
	    for(int i = 0;i<n;i++){
	        select(arr,i);
	    }
	}
}

Bubble Sort - Time Complexity:O(n2)

Insertion Sort

Problem

Solution

import java.util.*;
class solution
{
    public static void main(String args[])
    {    
        Scanner S = new Scanner(System.in);
        int size = S.nextInt();
        int arr[] = new int[size];
        for(int i = 0;i<size;i++){
            arr[i] = S.nextInt();
        }
        insertionsort(arr,size);
    }
    static void insertionsort(int arr[],int size){
        for(int i = 0;i<arr.length;i++)
        {
            int j = i;
            while(j>0 && arr[j - 1] > arr[j])
            {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                j--;
                System.out.print("ret"+" ");
            }
        }
    }
}

Time COmplexity: O(n)

Simplest Solution using Sort method

class solution
{
	int insert(int arr[], int n)
	{
        // code here such that InsertionSort sorts arr[]
        return arr[n];
	}
	
	void Insertionsort(int arr[], int n)
	{
	    //code here
	    Arrays.sort(arr);
	    for(int i = 0;i<n;i++){
	        insert(arr,i);
	    }
	}
}

Insertion Sort - Time Complexity:O(n2)

Merge Sort

Problem

SOlution

 public static void mergeSort(int[] arr, int numberOfElements) {
    if (numberOfElements < 2) {
      return;
    }

    // Find the middle position and create left and right partitions
    int mid = numberOfElements/2;
    int[] leftArr = new int[mid];
    int[] rightArr = new int[numberOfElements - mid];

    // Fill up the partitions
    for (int i = 0; i < mid; i++) {
      leftArr[i] = arr[i];
    }
    
    for (int i = mid; i < numberOfElements; i++) {
      rightArr[i- mid] = arr[i];
    }

    // Apply merge sort on the left parition
    mergeSort(leftArr, mid);

    // Apply merge sort on the right partition
    mergeSort(rightArr, numberOfElements  - mid);

    // Finally merge the partitions
    merge(arr, leftArr, rightArr, mid, numberOfElements - mid);
  }

  private static void merge(int[] arr, int[] leftArr, int[] rightArr, int left, int right) {
    int i = 0, j = 0, k = 0;

    // Merge arrays based on the smaller values
    while (i < left && j < right) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k++] = leftArr[i++];
      }
      else {
        arr[k++] = rightArr[j++];
      }
    }

    // Fill out remaining values if any
    while (i < left) {
      arr[k++] = leftArr[i++];
    }
    while (j < right) {
      arr[k++] = rightArr[j++];
    }
  }

Quick Sort

Problem

Solution

 public static void quickSort(int[] arr, int begin, int end) {

    if (begin < end) {
      // Find the partition
      int partition = findPartition(arr, begin, end);

      // Do quick sort on the left part
      quickSort(arr, begin, partition - 1);

      // Do quick sort on the right part
      quickSort(arr, partition + 1, end);
    }
  }

  private static int findPartition(int[] arr, int begin, int end) {

    // Taking last element as pivot element
    int pivot = arr[end];

    int i = (begin - 1); // index of smaller element

    for (int j = begin; j < end; j++) {
      // If current element is smaller than the pivot
      if (arr[j] < pivot) {
        i++;

        // swap arr[i] and arr[j]
        swap(arr, i, j);
      }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    swap(arr, i + 1, end);

    return i + 1;
  }

  private static void swap(int[] arr, int i, int j) {
    int swapTemp = arr[i];
    arr[i] = arr[j];
    arr[j] = swapTemp;
  }

Recursive Bubble Sort and Merge Sort

Recursive Bubble sort Problem

Recursive Insertion Sort Problem

Solution

Arrays.sort(arr);

Arrays

Largest element In an array

Problem

Solution

class Solution {
    public static int largest(int n, int[] arr) {
        // code here
        int larg = arr[0];
        for(int i = 0;i<n;i++){
            if(arr[i]>larg){
                larg = arr[i];
            }
        }
        return larg;
    }
}

Second Largest element in an array (Very Important Interview Question)

Problem

Solution

using java Collections

class Solution {
    public int print2largest(List<Integer> arr) {
        // Code Here
        Collections.sort(arr);
        int n = arr.size();
        if(n<2){
            return -1;
        }
        
        int x = arr.get(n - 1);
        for(int i = n - 2;i>=0;i--){
            if(arr.get(i) != x){
                return arr.get(i);
            }
        }
        return -1;
        
    }
}

Brute Solution

1.

import java.util.*;
class solution{
public static int secondlargest(int arr[],int n){
int n = arr.length;
if(n == 0 || n==1){
return -1;
}
Arrays.sort(arr);
int largest = arr[n - 2];
System.out.println(largest);
}

import java.util.*;
public class solution{
public static int secondlargest(int arr[],int n){
int firstlargest  = arr[n - 1];
int seconlrgt = 0;
for(int i = n - 2;i>=0;i--){
if(arr[i] != firstlargest){
      secondlrgt = arr[i];
      break;
    }
 }
System.out.println(secondlrgt);
}
}

Pseudocode

* Brute Force Pseudocode

* Better Approach pseudocode

Arrays Is Sorted

Problem

Answer

If Array is sorted and rotated

class Solution {
    public boolean check(int[] nums) {

     int count  = 0;
     for(int i = 0;i<nums.length;i++){
            if(nums[i] > nums[(i+1) % nums.length]){
                count++;
            }
        } 
        if(count > 1){
            return false;
        }  
        return true;
    }
}

If array is sorted

Solution

class Solution {
    public boolean check(int[] nums) {

     int count  = 0;
     for(int i = 1;i<nums.length;i++){
            if(nums[i] > nums[(i+1)])
		return false; 
    }
	return true;
}

Remove Duplicate Element From Sorted Array

Problem

Solution

class Solution {
    public int removeDuplicates(int[] nums) {
         int len = nums.length;
         int i = 0;
            for(int j = 0;j<len;j++){
                if(nums[j] != nums[i]){
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i + 1;
    }
}

Pseudocode

Time Complexity: O(n) Space Complexity: O(1)

Rotate an Array by 1 place

class solution{
public void rotatesinglearray(int arr[],int k){
int temp  = arr[0];
for(int i = 1;i<k;i++){
arr[i - 1] = arr[i];
	}
int lastindex = temp;
return arr;
}

Time Complexity: O(n) Space Complexity: O(1)

Rotate an array by d places

Problem

Solution

class Solution {
    public void rotate(int[] nums, int k) {
    k = k%nums.length;    
    // reverse an array
    reverse(nums,0,nums.length - 1);
    // reverse an array up to the index k;
    reverse(nums,0,k - 1);
    //reverse an array after k up to endindex;
    reverse(nums,k,nums.length - 1);
    }
    public void reverse(int[] nums,int startindex,int endindex){
        while(startindex<endindex){
            int temp = nums[startindex];
            nums[startindex] = nums[endindex];
            nums[endindex] = temp;
            startindex++;
            endindex--;
        }
    }
}

Time Complexity: O(n) Space Complexity: O(1)

Moves Zero To end

Problem

Solution

class Solution {
    public void moveZeroes(int[] nums) {
        //array length
        int len = nums.length;
        // array check for base case;
        if(len<2){
            return;
        }
        int slow = 0;
        int fast = 0;
        while(fast < len){
            if(nums[fast] != 0){
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                slow++;
                fast++;
            }
            else{
                fast++;
            }
        }
    }
}

Time Complexity: O(n) and Space Complexity:O(1)

Linear Search

Problem

Solution

class Solution {
    static int searchInSorted(int arr[], int N, int K) {
        for(int i = 0;i<N;i++){
            if(arr[i] == K){
                return 1;
            }
        }
        return -1;
        // Your code here
    }
}

Time Complexity: O(Log N) and Space Complexity:O(1)

Union of Sorted Array

Problem

Solution

class Solution
{
    //Function to return a list containing the union of the two arrays.
    public static ArrayList<Integer> findUnion(int arr1[], int arr2[], int n, int m)
    {
        // add your code here
        Set<Integer> result = new TreeSet<>();
        for(int i : arr1){
            result.add(i);
        }
        for(int j : arr2){
            result.add(j);
        }
        return new ArrayList<>(result);
    }
}

Time Complexity: O(n + m) and Space Complexity:O(n + m)

Find Missing Number in an array

Problem

Solution

class Solution {
    public int missingNumber(int[] nums) {
       int sums = 0;
       for(int i = 0;i<nums.length;i++){
        sums = sums + nums[i];
       }
       int actualsum = (nums.length * (nums.length + 1))/2;
       int res = actualsum - sums;
       return res; 
    }
}

Time Complexity: O(N) and Space Complexity:O(1)

Max Consecutive Ones

Problem

C++

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int maxi = 0;
        int count  = 0;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] == 1){
                count++;
                maxi = max(maxi,count); 
            }
            else{
                count  =  0;
            }
        }
        return maxi;
    }
};

Java

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
     int maxi = 0;
     int count = 0;
     for(int i = 0;i<nums.length;i++){
        if(nums[i] == 1){
            count++;
            maxi = Math.max(count,maxi); 
        }
        else{
            count = 0;
        }
     } 
     return maxi;  
    }
}

Time Complexity:O(N) and Space complexity: O(1)

Longest Subarray With Sum K(Positive and negative)

Problem

class Solution {
    // Function for finding maximum and value pair
    public static int lenOfLongSubarr(int A[], int N, int K) {
        // Complete the function
        HashMap<Integer,Integer> prevsum = new HashMap<>();
        int sum = 0,maxlen = 0;
        for(int i = 0;i<N;i++){
            sum = sum + A[i];
            if(sum == K){
                maxlen = i + 1;
            }
            if(!prevsum.containsKey(sum)){
               prevsum.put(sum, i);
            }
            if(prevsum.containsKey(sum - K)){
              maxlen = Math.max(maxlen, i - prevsum.get(sum - K));
            }
        }
        return maxlen;
        
    }
}

Two Sum

Problem

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        int res = 0;
        for(int row = 0;row<len;row++){
            for(int col = row + 1;col<len;col++){
                if(nums[row] + nums[col] == target){
                        return new int[]{row,col};
                }
            }
        }
        return new int[]{};
    }
}

Time Complexity: O(N2) and Space Complexity: O(1)

Sort 0 1 2

Problem

Solution

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = 0;i<len;i++){
            System.out.println(nums[i]);
        }
    }
}

Time Complexity: O(NLogN) and Space Complexity: O(1)

majority element

Problem

Solution

class Solution {
    public int majorityElement(int[] nums) {
        //arraylength
        int len = nums.length;
        //count 
        int count  = 1;
        //majority element
        int majority = nums[0];
        // check majority
        for(int i = 0;i<len;i++){
            if(nums[i] == majority){
                count = count + 1;
            }
            else{
                count = count - 1;
                if(count == 0){
                    majority = nums[i];
                    count = 1;
                }
            }
        }
        return majority;
    }
}

Time Complexity: O(N) and Space Complexity: O(1)

Maximum Subarray

Problem

Solution

class Solution {
   public int maxSubArray(int[] nums) {
       // length
       int len = nums.length;
       // sum
       int sum = 0;
       // max sum
       int max_sum = nums[0];
       // check using kadane Algorithm
       for(int i = 0;i<len;i++){
           sum = sum + nums[i];
           max_sum = Math.max(max_sum,sum); 
           if(sum<0){
               sum = 0;
           }
       }
       return max_sum;
   }
}

Time Complexity: O(N) and Space COmplexity: O(1)

Plus ONe

Problem

Solution

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i = digits.size() - 1;i>=0;i--){
            if(digits[i]<9){
                digits[i]++;
                return digits;
            }
            else{
                digits[i] = 0;
            }
        }
        digits.push_back(0);
        digits[0] = 1;
        return digits;
    }
};

Time Complexity: O(N) and Space COmplexity: O(1)

Maximum Score in Subarray

Problem

Solution

class Solution {
    // Function to find pair with maximum sum
    public int pairWithMaxSum(List<Integer> arr) {
        // Your code goes here
        int max = 0;
        int sum = 0;
        for(int i = 0;i<arr.size() - 1;i++){
            sum = arr.get(i) + arr.get(i + 1);
            max = Math.max(sum,max);
        }
        return max;
    }
}

Time Complexity: O(N) and Space COmplexity: O(1)

Buy Stock and Sell - I

Problem

Solution

class Solution {
    public int maxProfit(int[] prices) {
        //at the beginning the minimum is the first place
        int buy_price = prices[0];
        
        // profit
        int profit = 0;
        
    
        for(int  i = 1;i<prices.length;i++){

           // if current price is less than buy_price
            if(prices[i]<buy_price){
                buy_price = prices[i];
            }
            
            else{
                // else check if we can get better profit
                int current_profit = prices[i] - buy_price;
                profit = Math.max(current_profit,profit);
            }
            
        }
        return profit;
    }
}

Time Complexity: O(N) and Space COmplexity: O(1)

Rearrange Array Elements by Sign

Problem

Solution

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int len = nums.length;
        int positive = 0;
        int negative = 1;
        int[] fin = new int[len];
        for(int i = 0;i<len;i++){
            if(nums[i] < 0){
                fin[negative] = nums[i];
                negative = negative + 2;   
            }
            else{
                fin[positive] = nums[i];
                positive = positive + 2;
            }
        }
        return fin;
    }
}

Time Complexity: O(N) and Space COmplexity: O(1)

Subarray sums equals k

Problem

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n=0;
        for(int i=0; i<nums.length; i++)
        {
            int s=0;
            for(int j=i; j<nums.length; j++)
            {
                s+=nums[j];
                if(s==k)
                n++;
                
            }
        }
        return n;
    }
}

Time Complexity: O(N2) and Space COmplexity: O(1)

Array Leaders

Problem

Solution

class Solution {
    // Function to find the leaders in the array.
    static ArrayList<Integer> leaders(int n, int arr[]) {
        // Your code here
        // new arraylist
        ArrayList<Integer> list = new ArrayList<>();
        // max
        int max = arr[n - 1];
        // the value from reverse to check max
        for(int first = n - 1;first>=0;first--)
        {
            
            if(arr[first] >= max) 
            {
                list.add(0,arr[first]);
                max = arr[first];
            }
        }
        return list;
    }
}

Time Complexity: O(N) and Space COmplexity: O(1)

Longest Consecutive Sequence

Problem

Solution

class Solution {
   public int longestConsecutive(int[] nums) {
       int n = nums.length;
       if (n == 0)
           return 0;
   int longest = 1;
       Set<Integer> set = new HashSet<>();
       for (int i = 0; i < n; i++) {
           set.add(nums[i]);
       }
       for (int i : set) {
               if (!set.contains(i - 1)) {//check if 'i' is a starting number
               int cnt = 1;
               int tempIndex = i;
               while (set.contains(tempIndex + 1)) {
                   tempIndex++;
                   cnt++;
               }
               longest = Math.max(longest, cnt);
           }
       }
       return longest;
}

Time Complexity: O(Log N) and Space COmplexity: O(1)

Rotate Mtrix by 90 degree

Problem

Solution

	class Solution {
    public void rotate(int[][] matrix) {
        for(int i = 0;i<matrix.length;i++){
            for(int j = 0;j<i;j++){
                // swap the values using two pointer
                int temporary = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temporary;
            }
        }

        for(int i = 0;i<matrix.length;i++){
            for(int j = 0;j<matrix.length/2;j++){
                 // swap the values using two pointer with last value of row 
                int temporary = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length-1-j];
                matrix[i][matrix.length-1-j] = temporary;
            }
        }
    }
    }

Time Complexity: O(N*N) and Space COmplexity: O(1)

Spiral Matrix

Problem

Solution

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rowlen  = matrix.length;//row length
        int collen = matrix[0].length; //col length
        int left = 0;
        int right = collen - 1;
        int top = 0;
        int bottom = rowlen -1;
        List<Integer> list  = new ArrayList<>();
        while(top<=bottom && left<=right)
        {
            // left to right
            for(int i = left;i<=right;i++){
                list.add(matrix[top][i]);
            }
            top++;

            // top to bottom
            for(int i = top;i<=bottom;i++){
                list.add(matrix[i][right]);
            } 
            right--;


            // right to left (if still top is need to be less than bottom)
            if(top <= bottom){
                for(int i = right;i>=left;i--){
                    list.add(matrix[bottom][i]);
                }
            }
            bottom--;
            // bottom to top
            if(left<= right){
                for(int i = bottom;i>=top;i--){
                    list.add(matrix[i][left]);
                }
            }
            left++;
        }
        return list;
    }
} 

Time Complexity:O(M * N) and space Complexity: O(1)

Set Matrix Zeros

Problem

Solution

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstrow = false,firstcolumn = false;

        // set markers in first row and first column
        for(int i = 0;i<matrix.length;i++)
        {
            for(int j = 0;j<matrix[0].length;j++){
                if(matrix[i][j] == 0){
                    if(i == 0){
                       firstrow =  true;
                    }
                    if(j == 0){
                        firstcolumn = true;
                    }
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        // replace inner matrix
        for(int i = 1;i<matrix.length;i++){
            for(int j = 1;j<matrix[0].length;j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        if(firstrow){
            for(int j = 0;j<matrix[0].length;j++){
                    matrix[0][j] = 0;
            }
        }
        if(firstcolumn){
            for(int i = 0;i<matrix.length;i++){
                    matrix[i][0] = 0;
            }
        }
    }
}

Time Complexity:O(M * N) and space Complexity: O(1)

Next Permutation

Problem

Solution

class Solution {
    public void nextPermutation(int[] nums) {
        int ind1=-1;
        int ind2=-1;
        // step 1 find breaking point 
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                ind1=i;
                break;
            }
        }
        // if there is no breaking  point 
        if(ind1==-1){
            reverse(nums,0);
        }
        
        else{
            // step 2 find next greater element and swap with ind2
            for(int i=nums.length-1;i>=0;i--){
                if(nums[i]>nums[ind1]){
                    ind2=i;
                    break;
                }
            }

            swap(nums,ind1,ind2);
            // step 3 reverse the rest right half
            reverse(nums,ind1+1);
        }
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    void reverse(int[] nums,int start){
        int i=start;
        int j=nums.length-1;
        while(i<j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }
}

Time Complexity:O(N) and space Complexity: O(1)

Pascal Triangle

Problem

Solution

function pascalTriangle(n) {
    let ans = 1;
    console.log(ans + " "); // printing 1st element
  
    //Printing the rest of the part:
    for (let i = 1; i < n; i++) {
      ans = ans * (n - i);
      ans = ans / i;
      console.log(ans + " ");
    }
    console.log("n");
}
const n = 5;
pascalTriangle(n);

Time Complexity:O(N) and space Complexity: O(1)

Majority element n/3 times

Problem

Solution

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> uniqueNums = new HashSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }
        for (int num : uniqueNums) {
            int count = 0;
            for (int n : nums) {
                if (n == num) {
                    count++;
                }
            }
            if (count > nums.length / 3) {
                result.add(num);
            }
        }
        return result;
    }
}

Time Complexity:O(N2) and space Complexity: O(N)

Three Sum (Most Asked interview Problem)

Problem

Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        // check list length or null
        if(nums == null || nums.length < 3){
            return new ArrayList<>();
        }

        // sort
        Arrays.sort(nums);
        // set 
        Set<List<Integer>> result = new HashSet<>();
        
        // using two pointers 
        for(int i = 0;i<nums.length - 2;i++)
        {
            int left  = i + 1;
            int right = nums.length - 1;
            while(left <  right)
            {
                // sum nums values

                int sum = nums[i] + nums[left] + nums[right];

                //if sum is equal to zero
                if(sum == 0)
                {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                }

                else if(sum < 0)
                {
                    left++;
                }

                else
                {
                    right--;
                }
            }
        }
        return new ArrayList<>(result);
    }
}

Time Complexity:O(N2) and O(N)

Four SUm

Problem

Solution

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int size = nums.length;
        if (nums == null || size < 4) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < size - 3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i + 1; j < size - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j-1]) continue;
                int left = j + 1, right = size - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> res = new ArrayList<>();
                        res.add(nums[i]); res.add(nums[j]); res.add(nums[left]); res.add(nums[right]);
                        result.add(res);
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left-1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right+1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Maximum Product SubArray

Problem

Solution

class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int leftproduct = 1;
        int rightproduct = 1;
        int ans = nums[0];
        for(int i = 0;i<len;i++){
            if(leftproduct == 0){
                leftproduct = 1;   
            }
            if(rightproduct == 0){
                rightproduct = 1;
            }

            //leftproduct
            leftproduct = leftproduct * nums[i];

            //rightproduct
            rightproduct = rightproduct * nums[len - 1 - i];

            ans = Math.max(ans,Math.max(leftproduct,rightproduct)); 
        }
        return ans;
    }
}

Time Complexity:O(N) and Space COmplexity: O(1)

Merge Two SOrted Array

Problem

Solution

 for (int j = 0, i = m; j < n; j++) {
            nums1[i] = nums2[j];
            i++;
        }
        Arrays.sort(nums1);

Time Complexity:O(N lOgN) and SpaceCOmplexity: O(1)

Longest subarray with 0 sum

Problem

Solution

import java.util.HashMap;

class Solution {
    public int maxLen(int[] arr, int n) {
        // Your code here
        HashMap<Integer, Integer> mp = new HashMap<>();
        int sum = 0;
        int ans = 0;
        mp.put(0, -1);
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (mp.containsKey(sum)) {
                ans = Math.max(ans, i - mp.get(sum));
            } else {
                mp.put(sum, i);
            }
        }
        return ans;
    }
}

Time Complexity: O(n) and Space Complexity: o(n)

Sign of the Product array

Problem

Solution

class Solution {
    public int arraySign(int[] nums) {
        double result = 1;
        for(int i = 0;i<nums.length;i++){
            result = result * nums[i];
        }
        if(result < 0){
            return -1;
        }
        else if(result > 0){
            return 1;
        }
        else{
            return 0;
        }
    }
}

TIme Complexity: O(N) and Space Complexity: O(1)

Binary Search

Introduction

Problem

Solution

    public static int binarySearch(int[] nums, int target) {
        int n = nums.length; //size of the array.
        int low = 0, high = n - 1;

        // Perform the steps:
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return mid;
            else if (target > nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
} 

TIme Complexit:O(Log N) and Space Complexity: O(1)

Lower Bound

Problem

Solution

  class Solution {

  // Function to find floor of x
  // arr: input array
  // n is the size of array
  static int findFloor(long arr[], int n, long x) {
     int low=0,high=arr.length-1,ans=-1;
      while(low <= high){
          int mid=(low+high)/2;
          if(arr[mid] == x) return mid;
          else if(arr[mid] <= x){
              ans = mid;
              low=mid+1;
          }else{
              high=mid-1;
          }
      }
      return ans;
     }
  }

Time Complexity:O(Log2 N)and spcae complexity: O(1)

Upper Bound Bound

Solution

   class Solution {

   // Function to find floor of x
   // arr: input array
   // n is the size of array
   static int findFloor(long arr[], int n, long x) {
      int low=0,high=arr.length-1,ans=-1;
       while(low <= high){
           int mid=(low+high)/2;
           if(arr[mid] == x) return mid;
           else if(arr[mid] < x){
               ans = mid;
               low=mid+1;
           }else{
               high=mid-1;
           }
       }
       return ans;
      }
   }

Time Complexity:O(Log2 N)and space complexity: O(1)

Search Insert Position

Problem

Solution

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        int ans = nums.length;
        while(low<=high){
            int mid = (low + high)/2;
            if(nums[mid] >= target){
                ans = mid;
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        return ans;
    }
}

Time Complexity:O(Log2 N)and spcae complexity: O(1)

First and Last Occurence of a sorted array

Problem

Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
    // first
            int first = firstoccurence(nums,target);
    // last
            int last  =  lastoccurence(nums,target);
    
    return new int[]{first,last};
    }

    public static int firstoccurence(int[] nums,int target){


            int low = 0;
            int high = nums.length - 1;
            
            int first = -1;
            
            while(low<=high){
                int mid = (low + high)/2;
                if(nums[mid] == target){
                    first = mid;
                    high = mid - 1;
                }
                else if(nums[mid]<target){
                    low = mid + 1;
                }
                else{
                    high = mid - 1;
                }
            }
        return first;
    }

    public static int lastoccurence(int[] nums,int target){


            int low = 0;
            int high = nums.length - 1;
            
            int last = -1;
            
            while(low<=high){
                int mid = (low + high)/2;
                if(nums[mid] == target){
                    last = mid;
                    low = mid + 1;
                }
                else if(nums[mid]<target){
                    low = mid + 1;
                }
                else{
                    high = mid - 1;
                }
            }
        return last;
    }
}

Time Complexity :O(Log N) and Space Complexity:O(1)

Number of occurences

Problem

class Solution {
    int count(int[] arr, int n, int x) {
        // code here
        int count = 0;
        for(int i = 0;i<n;i++){
            if(arr[i] == x){
                count++;
            }
        }
        return count;
    }
}

Time Complexity:O(n) and Space Complexity:0(1)

Search Element in Rotated Array

Problem

Solution

class Solution {
    public int search(int[] nums, int target) {
        int ans  = -1;
        for(int i = 0;i<nums.length;i++){
            if(nums[i] == target){
                ans = i;
            }
        }
        return ans;
    }
}

Time COmplexity:O(N) and Space Complexity: O(1)

Search Element in Rotated Array II

Problem

Solution

class Solution {
    public boolean search(int[] nums, int target) {
       boolean ans  = true;
       for(int i = 0;i<nums.length;i++){
        if(nums[i] == target){
            return ans;
        }
       }
       return false; 
    }
}

Time COmplexity:O(N) and Space Complexity: O(1)

Find Minimum in Rotated Sorted Array

Problem

Solution

class Solution {
    public int findMin(int[] nums) 
    {
        Arrays.sort(nums);
        int min = nums[0];
        for(int i = 0;i<nums.length;i++){
            if(nums[i]<min){
                min = i;
            }
        }
        return min;
    }
}

Time Complexity:O(n Logn) and Space Complexity:O(1)

Find Kth Rotation

Problem

Solution

public int findKRotation(List<Integer> arr) {
        // Code here
       int low=0;
       int high=arr.size()-1;
       int ans=Integer.MAX_VALUE;
       int index=-1;
      
       
       while(low<=high){
            int mid=(low+high)/2;
           
           if(arr.get(low)<=arr.get(high)){
               if(arr.get(low)<ans){
                   index=low;
                   ans=arr.get(low);
                   
               }
               break;
           }
           //left part sorted.
           if(arr.get(low)<=arr.get(mid)){
               if(arr.get(low)<ans){
                   index=low;
                   ans=arr.get(low);
                   
               }
                   low=mid+1;
            
           }
           else{
               //right part sorted.
               if(arr.get(mid)<ans){
                   index=mid;
                   ans=arr.get(mid);
                   
               }
               high=mid-1;
               
           }
           
       }
       return index;
       
    }

Time Complexity: O(log2n) and Space Complexity: O(1)

Single Element in Sorted Array

Problem

Solution (Brute)

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for(int ans : nums){
            res = res ^ ans; 
        }
        return res;
    }
}

Time Complexity:O(n) and Space complexity: O(1)

Solution (Optimal)

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;  // Fix the initial value of right

        while (left <= right) {
            int mid = (left + right) / 2;

            // Check if mid is the single element by verifying its neighbors, ensuring mid is not at the boundary
            if ((mid == 0 || nums[mid] != nums[mid - 1]) && (mid == n - 1 || nums[mid] != nums[mid + 1])) {
                return nums[mid];
            }

            // Adjust binary search range based on even/odd index and matching conditions
            if ((mid % 2 == 0 && nums[mid] == nums[mid + 1]) || (mid % 2 == 1 && nums[mid] == nums[mid - 1])) {
                left = mid + 1;  // Single element is in the right half
            } else {
                right = mid - 1;  // Single element is in the left half
            }
        }

        return -1;  // Shouldn't reach here as there is always one non-duplicate element
    }
}

Time Complexity:O(Log n) and Space complexity: O(1)

Find The Peak Element

Problem

Solution

#include <vector>
#include <limits.h>

class Solution {
public:
    int findPeakElement(std::vector<int>& nums) {
        int len = nums.size();
        if (len == 1) {
            return 0;
        }
        int max = INT_MIN, req = 0, res = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] > max) {
                max = nums[i];
                res = i;
                req = 1;
            }
        }
        if (req == 1) {
            return res;
        } else {
            return 0;
        }
    }
};

Time Complexity:O(N) and Space Complexity:O(1)

Find The Square root of a number in logn

Problem

Solution

class Solution {
    long floorSqrt(long n) {
        return (long)(Math.floor(Math.pow(n , 0.5)));
    }
}

Time COmplexity:O(1) and Space Complexity:O(1)

Find the Nth root of a number using binary search

Problem

Solution

class Solution
{
    public int NthRoot(int n, int m)
    {
        // code here
        int l=0;
        int r=m;
        
        while(l<=r){
            int mid=(l+r)/2;
            
            if(Math.pow(mid,n) == m){
                return mid;
            }
            
            else if(Math.pow(mid,n) < m){
                l=mid+1;
            }
            
            else{
                r=mid-1;
            }
        }
        return -1;
    }

Time Complexity:O(log m) and Space Complxity: O(1)

Find the kth missing number

Problem

Solution

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int low = 0,high = arr.length - 1;
        while(low<=high){
            int mid = (low +  high)/2;
            int misnum = arr[mid] - (mid + 1);
            if(misnum < k){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return k + high + 1;
    }
}

Time Complexity: O(n) and Space Complexity: O(1)

Merge of Two Sorted arrays

Problem

Solution

class Solution {
    public long kthElement(int k, int arr1[], int arr2[]) {
        // code here
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i<arr1.length;i++){
            list.add(arr1[i]);
        }
        for(int i = 0;i<arr2.length;i++){
            list.add(arr2[i]);
        }
        Collections.sort(list);
        return list.get( k - 1);
    }
}

Time Complexity: O((n+m)log(n+m)) and Space Complexity: O(1)

Find The Smallest Divisor

Problem

Solution

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        Arrays.sort(nums);
        int low = 1,high = nums[nums.length - 1],ans = 1;

        while(low <= high){
            int mid = (low + high) / 2;
            int sum = 0;
            for(int i = 0;i<nums.length;i++)
            {
                sum  = sum + (int) Math.ceil((double)nums[i] / (double)mid);
            }
            if(sum<=threshold){
                ans = mid;
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        return ans;
    }
}

Time Complexity:O(N log(Max(nums))) and space complexity:O(1)

Capacity To Ship Packages Within D Days

Problem

Solution

class Solution {
    public int shipWithinDays(int[] weights, int D) 
    {
        // minimum capacity
        int minCap = 0;
        // maximum capacity 
        int maxCap = 0;
        for (int weight : weights) 
        {

      minCap = Math.max(minCap, weight);
      maxCap += weight;
        }

    // Apply binary search
    while (minCap < maxCap) {
      int mid = minCap + (maxCap - minCap) / 2;

      // Try to ship with "mid" capacity
      int days = 1;
      int sum = 0;
      for (int weight : weights) {
        if (sum + weight > mid) {
          days++;
          sum = 0;
        }
        sum += weight;
      }

      // If more days are required, increase capacity
      if (days > D)
        minCap = mid + 1;
      else
        maxCap = mid;
    }

    return minCap;
    }
}

Time Complexity:(O logn) and space complexity:O(1)

Merge TWO Sorted Arrays

Problem

Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length,n2 = nums2.length;
        int i = 0,j = 0;
        int n = n1 + n2;

        // index2
        int ind2 = n / 2;
    
        // index1
        int ind1 = ind2 - 1;


        // count
        int count = 0;

        // index element 1
        int ind1el = -1;
        // index element 2
        int ind2el = -1;

        // running loops
        while(i < n1 && j < n2)
        {
            // nums1 is less than nums2
            if(nums1[i] < nums2[j])
            {

                // index1 is equalto  count
                if(count == ind1){
                    ind1el = nums1[i];
                }
                // index1 is equato count 
                if(count == ind2){
                    ind2el = nums1[i];
                }
                count++;
                i++;
            }
            
            // nums2 is less than nums1
            else{

                // index1 is equalto  count
                if(count == ind1){
                    ind1el = nums2[j];
                }
                // index1 is equato count 
                if(count == ind2){
                    ind2el = nums2[j];
                }
                count++;
                j++;
            }
        }
        while (i<n1)
        {
            // index1 is equalto  count
                if(count == ind1){
                    ind1el = nums1[i];
                }
                // index1 is equato count 
                if(count == ind2){
                    ind2el = nums1[i];
                }
                count++;
                i++;
        }
        while( j<n2)
        {
            // index1 is equalto  count
                if(count == ind1){
                    ind1el = nums2[j];
                }
                // index1 is equato count 
                if(count == ind2)
                {
                    ind2el = nums2[j];
                }
                count++;
                j++;
        }
        if(n %2 == 1){
            return ind2el;
        }

        return (double)((double)(ind1el + ind2el)) / 2.0;
    }
}

Time Complexity:O log(m + n) and Space Complexity: O(1)

Allocate Books

Problem

Solution

#include<bits/stdc++.h>

int countstudents(vector<int> &arr,int pages){
        int students = 1;
        long long pagestudent = 0;
        for(int i = 0;i<arr.size();i++){
            if(pagestudent + arr[i] <= pages){
                pagestudent += arr[i];
            }
            else{
                students = students + 1;
                pagestudent = arr[i];
            }
        } 
    return students;
}


int findPages(vector<int>& arr, int n, int m) {
    // Write your code here.
    if(m>n) return -1;
    int low = *max_element(arr.begin(),arr.end());
    int high = accumulate(arr.begin(),arr.end(),0);


    while(low <= high){
        int mid = (low+high)/2;
        int students = countstudents(arr,mid);
        if(students>m){
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }

    return low;
}

Time Complexity: O(N∗Log(Sum(Arr))) and Space Complexity : O(1)

Largest sum array

Problem 1

Problem 2

Solution

#include<bits/stdc++.h>

int countstudents(vector<int> &arr,int pages){
        int students = 1;
        long long pagestudent = 0;
        for(int i = 0;i<arr.size();i++){
            if(pagestudent + arr[i] <= pages){
                pagestudent += arr[i];
            }
            else{
                students = students + 1;
                pagestudent = arr[i];
            }
        } 
    return students;
}


int findPages(vector<int>& arr, int n, int m) {
    // Write your code here.
    if(m>n) return -1;
    int low = *max_element(arr.begin(),arr.end());
    int high = accumulate(arr.begin(),arr.end(),0);


    while(low <= high){
        int mid = (low+high)/2;
        int students = countstudents(arr,mid);
        if(students>m){
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }

    return low;
}
int findLargestMinDistance(vector<int> &arr, int k)
{
    //    Write your code here.
    return findPages(arr,arr.size(),k);
}

Time Complexity: O(N∗Log(Sum(Arr))) and Space Complexity : O(1)

Row with max1's

Problem

Solution

class Solution {
    public int rowWithMax1s(int arr[][]) 
    {
       int ans = -1;
       int max = 0;
       for(int i = 0;i< arr.length;i++)
       {
          int count = 0;
           for(int j = 0;j<arr[i].length;j++)
           {
               if(arr[i][j] == 1){
                   count  = count + 1;
               }
           }
           if(count > max){
               max = count;
               ans = i;
           }
       }
       return ans;
        
    }
}

Time coMPLExity:O(n * m) and space complexity:O(1)

Search an 2d matrix array

Problem

Solution

class Solution {
    searchMatrix(matrix, target) {
        let ans = true;
        for (let m = 0; m < matrix.length; m++) {
            for (let n = 0; n < matrix[m].length; n++) {
                if (matrix[m][n] === target) {
                    return ans;
                }
            }
        }
        return false;
    }
}

Time Complexity:O(m * n) and Space complexity:O(1)

Search an 2d matrix array

Problem

Solution

class Solution {
    searchMatrix(matrix, target) {
        let ans = true;
        for (let m = 0; m < matrix.length; m++) {
            for (let n = 0; n < matrix[m].length; n++) {
                if (matrix[m][n] === target) {
                    return ans;
                }
            }
        }
        return false;
    }
}

Time Complexity:O(m * n) and Space complexity:O(1)

Find The Peak ELement II

Problem

Solution

class Solution {
    public int[] findPeakGrid(int[][] matrix) {
        // using binary search 
        int low = 0;
        int high = matrix[0].length - 1;
        while(low <= high){
            // mid value
            int mid = (low+high) / 2;
            int row = maxiele(matrix,mid);
            int left = mid - 1>=0 ? matrix[row][mid - 1] : -1;
            int right = mid + 1< matrix[0].length?matrix[row][mid+1] : -1;
            if(matrix[row][mid]>left&&matrix[row][mid]>right) {
                return new int[]{row,mid};
            }
            else if(matrix[row][mid]<left) {
                high=mid-1;
            }
            else {
                low=mid+1;
            }
        }
        return new int[]{-1,-1};
    }

    // to find maximum element
    public int maxiele(int[][] array,int column){
        // max element
        int max = Integer.MIN_VALUE;
        int row = -1;
        for(int m = 0;m<array.length;m++){
            if(max<array[m][column]){
                max = array[m][column];
                row  = m;
            }
        } 
        return row;
    }
}

Time Complexity:O(LOg m) and Space complexity:O(1)

String

Find the Difference

Problem

Solution

class Solution {
    public char findTheDifference(String s, String t) {
        int total = 0;
        for(int i = 0;i<t.length();i++){
            total = total + t.charAt(i);
        }

        for(int i = 0;i<s.length();i++){
            total = total - s.charAt(i);
        }

        return (char)total;
    }
}

Merge String Alternatively

Problem

Solution

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        //two pointers
        int i = 0;
        int j = 0;
        // empty string
        string res = "";
        // size
        while(i<word1.size() && j<word2.size()){ // size from 0 to length of word
            res += word1[i++];
            res += word2[j++];
        }
        // i
        while(i<word1.size()){
            res += word1[i++];
        }
        // j
        while(j<word2.size()){
            res += word2[j++];
        }
        return res;
    }
};

Complexity

Time complexity:O(N + M)

Space complexity:O(N + M)

Find-the-index-of-the-first-occurrence-in-a-string

Problem

Solution

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i = 0;i<haystack.length() - needle.length() + 1;i++){
            if(haystack.charAt(i) == needle.charAt(0)){
                if(haystack.substring(i,needle.length() + i).equals(needle)){
                    return i;
                }
            }
        }
        return -1; 
    }
}

Valid Anagram

Problem

Solution

class Solution {
    public boolean isAnagram(String s, String t) {
        // length
        if(s.length() != t.length())return false;

        //change to charArray
        char a[] = s.toCharArray();
        char b[] = t.toCharArray();

        // sort
        Arrays.sort(a);
        Arrays.sort(b);

        // check value 
        for(int i = 0;i<a.length;i++){
            if(a[i]!=b[i]){
                return false;
            }
        }
        return true;
    }
}

Rotate a string

Problem

Solution

class Solution 
{
    public boolean rotateString(String s, String goal) {
        return (s.length() == goal.length() && (s+s).contains(goal));
    }
}

Time Complexity: O(n) and Space Complexity: O(1)

Isomorphic String

Problem

Solution

class Solution {
    public boolean isIsomorphic(String s, String t) {
        // create array to store index of characters in both strings
        int[] indexs = new int[200];
        int[] indext = new int[200];

        // if the length is not equal then return false
        if(s.length() != t.length()){
            return false;
        }

        //iterate through each charaters
        for(int i = 0;i<s.length();i++){
            if(indexs[s.charAt(i)] != indext[t.charAt(i)]){
                return false;
            }
            indexs[s.charAt(i)] = i + 1;
            indext[t.charAt(i)] = i + 1;
        }
        return true;
    }
}

Time Complexity:O(n) and Space Complexity: O(1)

Longest prefix

Problem

Solution

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        if (strs.length == 1) {
            return strs[0];
        }

        int prefixEnd = 0;
        while (true) {
            for (int i = 0; i < strs.length - 1; i++) {
                if (prefixEnd >= strs[i].length() || prefixEnd >= strs[i+1].length())
                    return strs[0].substring(0, prefixEnd);

                if (strs[i].charAt(prefixEnd) != strs[i + 1].charAt(prefixEnd))
                    return strs[0].substring(0, prefixEnd);
            }
            prefixEnd++;
        }
    }
}

Time Complexity: O(n * m) and space complexity: O(1)

Longest Odd Number in a string

Problem

class Solution {
    public String largestOddNumber(String num) {
        if(num.length() == 0) return "";
        for(int i = num.length() - 1;i>=0;i--){
            char res = num.charAt(i);
            if(res % 2 == 1){
                return num.substring(0,i+1);
            }
        }
        return "";
    }
}

Tim complexity: o(n) and space complexity:O(1)

largest 3-same digit number in a string

Problem

class Solution {
    public String largestGoodInteger(String num) {
        
 
        String[] sequences = {"999", "888", "777", "666", "555", "444", "333", "222", "111", "000"};

        for (String seq : sequences) {
            if (num.contains(seq)) {
                return seq;
            }
        }
        return "";
    }
}

Tim complexity: o(n) and space complexity:O(1)

Remove Valid Parenthesis

Problem

Solution

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder str = new StringBuilder();
        int cnt = 0;
        char[] ch = s.toCharArray();
        int n = ch.length;

        for(int i = 1; i < n; ++i) {
            if(ch[i] == '(') {
                cnt++;
                str.append('(');
            }
            else {
                if(cnt == 0) i++;
                else {
                    cnt--;
                    str.append(')');
                }
            }
        }
        return str.toString();
    }
}

Time Complexity:O(N) and Space Complexity: O(1)

Reverse Words in a string

Problem

Solution

class Solution {
    public String reverseWords(String s) {
        String[] arr = s.split(" +"); // use split function and regex 
        StringBuilder res = new StringBuilder();
        for(int index = arr.length - 1;index>=0;index--){
                res.append(arr[index]);
                res.append(" ");
        } 
        return res.toString().trim();
    }
}

Time Complexity:O(N) and Space Complexity: O(1)

Maximum Nesting Depth of parenthesis

Problem

Solution

class Solution {
    public int maxDepth(String s) {
        int soln = 0,count = 0;
        for(char req : s.toCharArray()){
            if(req == '('){
                count++;
            }
            else if(req == ')'){
                count--;
            }
            soln = Math.max(soln,count);
        }
        return soln;
    }
}

Time Complexity: O(N) and Space Complexity:O(1)

Roman to Integer

Problem

Solution

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> ans = new  HashMap<>();
        ans.put('I',1);
        ans.put('V',5);
        ans.put('X',10);
        ans.put('L',50);
        ans.put('C',100);
        ans.put('D',500);
        ans.put('M',1000);
         
        int result = ans.get(s.charAt(s.length() - 1));
        for(int i = s.length() - 2;i>=0;i--){
            if(ans.get(s.charAt(i)) < ans.get(s.charAt(i + 1))){
                result = result - ans.get(s.charAt(i));
            }
            else{
                result = result + ans.get(s.charAt(i));
            }
        }
        return result;
    }
}

Time Complexity: O(N) and Space Complexity:O(1)

Length of a last word

Problem

Solution

class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        int count = 0;
        for(int index = s.length() - 1;index >= 0;index--){
            if(s.charAt(index) == ' '){
                break;
            }
            count = count + 1;
        }
        return count;
    }
}

Time Complexity: O(N) and Space Complexity:O(1)

String to Integer (Atoi)

Problem

Solution

long long int myAtoi(char* s) {
    long long int i=0,sum=0,f=0;
    char si='+';
    while(s[i]!='\0')
    {
        if(s[i]=='-'&&f==0)
        {
            si='-';
            f=1;
        }
        else if(s[i]=='+'&&f==0)
        {
            si='+';
            f=1;
        }
        else if(s[i]==' '&&f==0)
        {

        }
        else if(s[i]>='0'&&s[i]<='9')
        {
            if(sum>INT_MAX)
            {
                goto z;
            }
            sum=sum*10+(s[i]-'0');
            if(!isdigit(s[i+1]))
            {
                break;
            }
            
        }
        else 
        {
            break;
        }
       
        i++;
    }
    z:
    if(si=='-')
    {
        sum*=-1;
        if(sum<INT_MIN)
        {
            return INT_MIN;
        }
        return sum; 
    }
    else
    {
        if(sum>INT_MAX)
        {
            return INT_MAX;
        }
        return sum;
    }
  
}

Time Complexity: O(N) and Space Complexity:O(1)

Longest Palindrome Substring

Problem

Solution

class Solution {
      public int l = 0;
    public int r = 0;

    public void func(char[] ch, int i) {
        if (i >= ch.length) return;
        int s = i;
        int e = i;
        while (e < ch.length - 1 && ch[e] == ch[e + 1]) e++;
        i=e;
        while (s >= 0 && e < ch.length && ch[s] == ch[e]) {
            s--;
            e++;
        }
        s++;
        e--;
        if (e - s > r - l) {
            r = e;
            l = s;
        }
        func(ch, i + 1);
    }

    public String longestPalindrome(String s) {
        char[] ch = s.toCharArray();
        func(ch, 0);
        return s.substring(l, r + 1);
    }
}

Time Complexity: O(N) and Space Complexity:O(1)

Linked List - Single,Double,Circular

Pseudocode to Construct Single Linked List

class Node{
    
    int data;
    Node next;
    
    // linkedlist starts. 
    Node(int data1,Node next1){
        this.data = data1;
        this.next = next1;
    }
    
    //linkedlist ends.
    
    Node(int data1){
        this.data = data1;
        this.next = null;
    }
}
public class Main
{
	public static void main(String[] args) {
		System.out.println("linked list");
		
		int arr[] = {2,4,5,2,24,2};
		
		Node av = new Node(arr[2]);
		System.out.println(av.data);
	}
}

Linked List nOtes from Kunal Kushawaha

private class LL
{
	private Node head;
	private Node tail; 
	class Node
	{
		// reference variables
		private int value;
		private Node data;

		// constructor
		public Node(int value){
			this.value =  value;
		}

		public Node(int value,Node node){

			this.value = value;
			this.node  = node; 
		}
	}
	// size
	private int size;
	// constructor
	public LL(){
		this.size = 0;
	}

        public void insert(int value){
		Node node = new Node(value);
		node.next = head;
		head = node;
		if(tail == null){
			tail = head;
		}
		size++;
	}
}

public class Main
{

	public static void main(String args[])
	{
		LL list  = new LL();
	}
}

Problem

Solution

class Solution {
    static Node constructLL(int[] arr) {
        // code here
        // null 
        Node ptr = new Node(0);
        // assign head as array first value
        Node head = new Node(arr[0]);
        
        ptr = head;
        
        for(int i = 1;i<arr.length;i++){
            Node temp = new Node(arr[i]);
            ptr.next = temp;
            ptr = temp;
        }
        
        return head;
        
    }
}