A Comprehensive Guide to Algorithms

4.2.1. Definition

4.2.2. How to count primitive operations

4.2.3. Examples

1. Example 1
   

   S1: curMax ← A[0]
   S2: i← 1
   S3: while i <= (n-1) do
   S4:     if curMax < A[i] then
   S5:         curMax ← A[i]
   S6:     i ← i+1;
   S7: return curmax
   

   Statement	Primitive Operation(s)	Time	Explanation
   S1	<- , A[0]	2	Assignment, Indexing
   S2	<-	1	Assignment
   S3	<= , n-1	2n	Logical, Arithmetic done n times
   S4	< , A[i]	2(n-1)	Logical, Indexing done (n-1) times
   S5	<- , A[i]	0 to 2(n-1)	Assigment, Indexing: Best Case to Worst Case
   S6	<- , i+1	2(n-1)	Assignment, Arithmetic done (n-1) times
   S7	return	1	Return

   • Time taken for Best Case: \(g(n) = 6n\)
   • Time taken for Worst Case: \(g(n) = 8n-2\)
2. Example 2
   

   def main():
       a=5
       b=6
       c=10
       for i in range(n):
           for j in range(n):
               x = i*i
               y = j*j
               z = i*j
           for k in range(n):
               w = a*k + 45
               v = b*b
           d = 33
   main()
   
   

   Statement	Primitive Operation(s)	Time	Explanation
   S1			def main is just a function definition
   S2	=	1	Assignment
   S3	=	1	Assignment
   S4	=	1	Assignment
   S5			for i in range(n) is just a loop definition
   S6			for j in range(n) is just a loop definition
   S7	=, *	2n2	Assignment, Arithmetic happening n2 times
   S8	=, *	2n2	Assignment, Arithmetic happening n2 times
   S9	=, *	2n2	Assignment, Arithmetic happening n2 times
   S10			for k in range(n) is just a loop definition
   S11	=, *, +	3n2	Assignment, Arithmetic, Arithmetic happening n2 times
   S12	=, *	2n2	Assignment, Arithmetic happening n2 times
   S13	=	n	Assignment happening n2 times
   S14	main()	1	Function Call

   Time taken: \(g(n) = 11n^{2} + 4\)

3. Example 3
   

   void g(int n){
       for(int i=0; i<n; ++i)
           for(int j=0; j<=i; ++j)
               f();
   }
   

   We’ll drop the constants because we’re only concered about how the runtime is related to n.

   Statement	Primitive Operation(s)	Time	Explanation
   S1			Function definition
   S2			Loop definition
   S3			Loop definition
   S4	f()	(1+2+3+4+...+n) * runtime of f()	Loop’s counter variable is dependent on n

   • On working through the program’s flow:
     • Iteration 1 of the outerloop: f() runs once, because (j<=i) is satisfied (j=0)
     • Iteration 2 of the outerloop: f() runs twice (j=0, j=1)
     • Iteration 3 of the outerloop: f() runs thrice (j=0, j=1, j=2)
     • …
     • Iteration n of the outerloop: f() runs n times
   • So, the runtime is (1+2+3+...+n) = \( \frac{n(n+1)}{2}\) * runtime of \(f()\)
4. Example 4
   

   function isPrime(n) {
       for (i = 2; i <= sqrt(n); ++i){
           if (n % i == 0){
               return false;
           }
       }
       return true;
   }
   
   

   Statement	Primitive Operation(s)	Time	Explanation
   S1			function definition
   S2			loop definition
   S3	%, ==	2(√n-2)	Whatever is inside the if block may/may not be executed 2√(n-2) times, but the condition is definitely being checked that many times

   • So the runtime is \(\sqrt{n}\)
5. Example 5
   

   int a = 0, i = N;
   while (i > 0){
       a += i;
       i /= 2;
   }
   
   

   Statement	Primitive Operation(s)	Time	Explanation
   S1	=, =	2	Assignment, Assignment
   S2			loop initialization
   S3	=, +	2(log2(n))	Assignment, Arithmetic running \(log_{2}(n)\) times

   • On looking at S4, we find that the loop counter variable keeps halving.
   • let’s work through the program flow, assuming \(n=16\). Hence i=16 too
     • Iteration 1: a+=16 happens, and now i = 8
     • Iteration 2: a+=8 happens, and now i = 4
     • Iteration 3: a+=4 happens, and now i = 2
     • Iteration 4: a+=2 happens, and now i = 1
     • Iteration 5: a+=1 happens, and now i = 0 (i is an integer, so 0.5 is basically 0)
   • \(n = 16\) meant 5 iterations \(5 = log_{2}(16) + 1\)
   • Hence, if a loop as a counter variable dividing itself by \(k\), then the number of iterations is \(log_{k}(n)\).
6. Example 6
   

   //Determines the value of the largest element in a given array
   //Input: An array A[0..n − 1]of real numbers
   //Output: The value of the largest element in A
   
   maxval <- A[0]
   for i <- 1 to (n−1) do
           if A[i]>maxval then
                   maxval <- A[i]
   return maxval
   
   

   Statement	Primitive Operation(s)	Time	Explanation
   S1	<- , A[0]	2	Assignment, Indexing
   S2			Loop Definition
   S3	A[i], >	2(n-2)	Indexing, Logical happening n times
   S4	<-, A[i]	0 to 2(n-2)	Assignment, Indexing, depends on the condition
   S5	return	1	return statement

   • Best Case = \( 2n-1 \)
   • Worst Case = \( 4n-5 \)
   • Overall time complexity = \( O(n) \)

4.3.1. The worst case, denoted by O (Big-Oh)

• Denoted by \( O(g(n)) \)
• It’s a set that contains any multiple of the growth rate of the worst scenario possible, and the growth rates of all the cases better than this.
• So when we say an algorithm has a complexity of \( O(g(n)) \) , it means that it’s order of growth is definitely less than any multiple of \(g(n)\).
• Some examples:
  1. \( n \subseteq O(n^{2}) \).
  2. \( \frac{1}{2} n (n-1) \subseteq O(n^{2}) \)
  3. \( an^{2} \subseteq O(n^{2}) \)
  4. \( an^{3} + bn^{2} + cn + d \subseteq O(n^{3})\)
• The last example might seem a little strange because \(an^{3} + bn^{2} + cn + d\) seems like a superset to \(n^{3}\), not a subset.

The reason for this is because \(n\) is a very large value. At such large values, the contribution of \( n^{3} \) is way more significant than the other terms, and at that point, it’s pretty much equal to \(n^{2}\).

• Say we have \( 5n^{3} + 2n^{2} \).

  • Let \( f1(n) = 5n^{3}\)

    

  • \( f2(n) = 2n^2 \)

    

  • \(g(n) = f1(n) + f2(n)\)

    

At very large values of \(n\) , \(g(n)\) pretty much converges with \(f1(n)\).

• Here’s some more examples, involving a little bit of calculation:
  • \( (n^{2} + 1 )^{10} \subseteq O(n^{20}) \)
  • \( 2^{nlog_{2} (n+2)} + (n+2)^{2}log(n) \)
    = \( (n+2)^{n} + (n+2)log(n) \)
    = \( \subseteq O(n^{n}) \)

4.3.2. The best case, denoted by ω (Big-Omega)

4.3.3. The average case, denoted by Θ (Big-theta)

4.4.1. Asymptote

4.4.2. Asymptotic efficiency and runtime complexity

4.4.3. Asymptotically tight or loose

4.4.4. Some complexities to keep in mind

1. Common growth rates, arranged in order
   

   \[ O(1) < O( log(n) ) < O( n^{x} ) < O( x^{n} ) < O( n!) \] for \(1\)<\(x\)<<n

   1. Example 1
      
      • Compare growth rate of \(O(n)\) and \(O(n^{2}) \)
      • Answer: \( O(n) \subseteq O(n^{2}) \) because both are in the form \( O(n^{x}) \), but the exponent of the right side is larger than the exponent of the left
   2. Example 2
      
      • Find the overall growth rate of \( log(n^{10}) + \sqrt{n}\)
      • Answer: \( g(n) = \sqrt{n} \)
      • This is because \( \sqrt{n} = n^{0.5} \). This has a higher growth rate than \( 10log(n) \text{ } (\because log(n^{a}) = alog(n) ) \).
   3. Example 3
      
      • Compare growth rates of \(nlog(n)\) and \( \sqrt{n} \)
      • Answer: \( nlog(n) \subseteq \omega(\sqrt{n}) \)
      • Explanation: \(n\) is definitely higher than \(\sqrt{n}\), but the answer becomes uncertain because of \(log(n)\) being multiplied to it. \(log(n)\) is definitely greater than \(1\) at high values of \(n\), and hence \(log(n)\) won’t scale down \(n\). Hence \(nlog(n)\) is higher than \(\sqrt{n}\).
2. Stirling’s approximation of n!
   
   • \( n! \approx \sqrt{2 \pi n} * (\frac{n}{e})^{n} \), at very large values of n.
   • On taking log on both sides, \( log(n!) \approx log(\sqrt{2 \pi n} * (\frac{n}{e})^{n} ) \)
   • This simplifies to \( log(n!) \approx nlog(n) \)
3. Growth rates of Logarithmic functions don’t depend on base
   
   • For instance, \( log_{2}(n) \) and \( log_{8}(n) \), are pretty much the same in terms of complexity.

5.3.1. Principal Cases

1. \(o(g(n))\)
   
   • \( \lim_{n\to\infty} \frac{t(n)}{g(n)} = 0\) ⇒ \(t(n)\) has a significantly smaller growth rate than \(g(n)\)
   • \(t(n) \) is asymptotically negligible when compared to \(g(n)\)
2. \(\theta(g(n))\)
   
   • \( \lim_{n\to\infty} \frac{t(n)}{g(n)} = c\) , where \(0
   • \(t(n) \) is an asymptotically tight bound when compared to \(g(n)\) as different multiples of \(g(n)\) are very close to \(t(n)\) and the entire thing is very tightly packed.
3. \(\omega(g(n))\)
   
   • \( \lim_{n\to\infty} \frac{t(n)}{g(n)} = \infty\) ⇒ \(t(n)\) has a larger growth rate than \(g(n)\)
   • \(t(n) \) is asymptotically dominant when compared to \(g(n)\)
4. \(O(g(n))\)
   
   • \( \lim_{n\to\infty} \frac{t(n)}{g(n)} < \infty\) ⇒ \(t(n)\) has a growth rate close to (but smaller than) a multiple of \(g(n)\).
   • \(g(n)\) is the asymptotic upper bound to \(t(n)\).
5. \(\Omega(g(n))\)
   
   • \( \lim_{n\to\infty} \frac{t(n)}{g(n)} > 0\) ⇒ \(t(n)\) has a growth rate close to (but larger than) a multiple of \(g(n)\).
   • \(g(n)\) is the asymptotic larger bound to \(t(n)\).

5.3.2. Explanation

5.3.3. How to use this

6.5.1. For Decreasing Functions

6.5.2. For Dividing Functions

9.7.1. Maximum Sum of ’K’ sized subarray

public class Main {
    public static void main(String[] args){
        System.out.println(maxSum(new int[]{5, -1, 3, 4}, 2));
    }
 
    static int maxSum(int[] arr, int k){
        int l=0, r=k-1, sum=0, maxSum;
        for(int i=0 ; i<=r ; sum+=arr[i++]);
        maxSum = sum;
        while(r<arr.length-1){
            sum-=arr[l++];
            sum+=arr[++r];
            maxSum = (sum>maxSum)? sum : maxSum;
        }
        return maxSum;
    }
}

7

9.7.2. Target Sum from a Pair of Numbers in a sorted array

public class Main {
    public static void main(String[] args){
        for(int x : pair(new int[]{1, 3, 9, 2}, 5))
            System.out.print(x+" ");
    }
    static int[] pair(int[] arr, int target){
        int l=0, r=arr.length-1, sum;
        while(l<r){
            sum = arr[l]+arr[r];
            if(sum == target)
                return new int[]{l, r};
            else if(sum > target)
                r--;
            else
                l++;
        }
        return new int[]{-1, -1};
    }
}

1 3 

9.7.3. Count the number of subarrays with sum <= k

public class Main {
    public static void main(String[] args){
        System.out.println(numberOfSubarrays(new int[]{1, 2, 3, 4}, 5));
    }
    static int numberOfSubarrays(int[] arr, int k) {
        int l = 0, sum = 0, count = 0;
        for(int r=0; r<arr.length ; r++){
            sum+=arr[r];
            while(sum>k) sum-=arr[l++];
            count+=(r - l + 1);
        }
        return count;
    }
}

6

9.8.1. Count the number of subarrays with sum<=k, but negative numbers exist

9.8.2. Count the number of subarrays with sum==k

import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args){
        System.out.println(numberOfSubarrays(new int[]{10, 2, -2, -20, 10}, -10));
    }
    static int numberOfSubarrays(int[] arr, int k){
        Map<Integer, Integer> count = new HashMap<>();
        int[] prefix = new int[arr.length];
        prefix[0] = arr[0];
        for(int i = 1; i < arr.length; i++)
            prefix[i] = arr[i] + prefix[i-1];
        count.put(0, 1);  
        int result = 0;
        for(int j=0 ; j<prefix.length ; j++){
            if(count.containsKey(prefix[j] - k))
                result+=count.get(prefix[j] - k);
            count.put(prefix[j], count.getOrDefault(prefix[j], 0) + 1);
//          the above line is the same as:
//          if(count.containsKey(prefix[j])) 
//              count.put(prefix[j], count.get(prefix[j]) + 1);
//          else count.put(prefix[j], 1);
        }
        
        return result;
    }
}

3

9.8.3. Binary Search

public class Main {
    static int binarySearch(int[] x, int key){
        int l = 0, r = x.length - 1, mid;
        while(l <= r){
            mid = (l + r) / 2;
            if(key > x[mid])
                l = mid + 1;
            else if(key < x[mid])
                r = mid - 1;
            else
                return mid;
        }
        return -1;
    }
 
    public static void main(String[] args){
        int[] x = {12, 24, 27, 35, 99};
        int index = binarySearch(x, 35);
        if(index > -1)
            System.out.println("Key found at index " + index);
        else
            System.out.println("Element not found in array.");
    }
}

Key found at index 3

11.1.1. Bubble Sort

1. Code
   

   public class Main {
       public static void bubbleSort(int[] x){
           int i, j, temp;
           for(i=0 ; i<x.length-1 ; i++)
               for(j=0 ; j<x.length-1-i ; j++)
                   if(x[j]>x[j+1]){
                       temp = x[j];
                       x[j] = x[j+1];
                       x[j+1] = temp;
                   }
       }
    
       public static void main(String[] args){
           int[] x = {12, 25, 2, 343, 99};
           bubbleSort(x);
           for(int i=0 ; i<x.length ; i++)
               System.out.print(x[i] + " ");
       }
   }
   
   

2. Worst Case Complexity
   

   Take the worst case scenario: x = [50, 40, 30 , 20, 10]

   Pass1	50	40	30	20	10
   50<->40	40	50	30	20	10
   50<->30	40	30	50	20	10
   50<->20	40	30	20	50	10
   50<->10	40	30	20	10	50
   Pass2	40	30	20	10	50
   40<->30	30	40	20	10	50
   40<->20	30	20	40	10	50
   40<->10	30	20	10	40	50
   Pass3	30	20	10	40	50
   30<->20	20	30	10	40	50
   30<->10	20	10	30	40	50
   Pass4	20	10	30	40	50
   20<->10	10	20	30	40	50

   • Let the number of elements by \(n\) (Here, \(n=4\))

   • Primitive Operation =

     
             temp = x[j];
             x[j] = x[j+1];
             x[j+1] = temp;
     
     

   • Primitive Operation (swapping) happens for \( \textnormal{n-1} + \textnormal{n-2} + \textnormal{n-3} + ... + 1 \) times
     = \( \frac{(n-1)(n)}{2} \) times ( \(\because\) sum of first \(n-1\) natural numbers)
     
   • So overall complexity = \(O(n^{2}) \)
3. Best Case Complexity
   

   The best case should occur when you already have a sorted array x = [10, 20, 30, 40, 50]

   Pass1	10	20	30	40	50
   	10	20	30	40	50
   	10	20	30	40	50
   	10	20	30	40	50

   • Primitive Operation happens for \(1+1+1+...\) times
     = \(n\) times
   • Overall complexity = \( \omega(n) \)
4. Properties
   
   • Bubble Sort is stable.
   • At the end of pass number \(i\), you get the \(i^{th}\) largest number of the array, at the \(i^{th} \) position from the end
   • The outer loop iterates through all the passes, and it runs for array.length-1 times.
   • The inner loop iterates through all the swaps ( \( \text{if element on the left} > \text{element on the right} \Rightarrow \text{swap} \) ), and it runs for array.length-1 - i times.
   • Bubble Sort is inplace.

11.1.2. Selection Sort

1. Code
   

   public class Main {
       public static void selectionSort(int[] x) {
           int i, j, min, temp;
           for (i = 0; i < x.length - 1; i++) {
               min = i;
               for (j = i + 1; j < x.length; j++)
                   if (x[j] < x[min])
                       min = j;
               temp = x[min];
               x[min] = x[i];
               x[i] = temp;
           }
       }
    
       public static void main(String[] args) {
           int[] x = {12, 25, 2, 343, 99};
           selectionSort(x);
        
           // Print the sorted array
           for (int i = 0; i < x.length; i++) {
               System.out.print(x[i] + " ");
           }
       }
   }
   
   

2. Worst Case Complexity
   

   Pass1	50	40	30	20	10
   min: 50 40	50	40	30	20	10
   min: 40 30	50	40	30	20	10
   min: 30 20	50	40	30	20	10
   min: 20 10, Swap(50,10)	50	40	30	20	10
   Pass2	10	40	30	20	50
   min: 40 30	10	40	30	20	50
   min: 30 20	10	40	30	20	50
   min: 20 (20<50), Swap(40,20)	10	40	30	20	50
   Pass3	10	20	30	40	50
   min: 30	10	20	30	40	50
   min: 30	10	20	30	40	50
   Pass4	10	20	30	40	50
   min: 40	10	20	30	40	50

   • There are two primitive operations here:

     1. Swapping min with correct element

             
                temp = x[min];
                x[min] = x[i];
                x[i] = temp;
        
        

        This happens \(n\) times.

     2. Comparing value of an array with minimum

             
                if (x[j] < x[min])
                        min = j;
        
        

3. Best Case Complexity
   

   Pass1	10	20	30	40	50
   min: 10	10	20	30	40	50
   min: 10	10	20	30	40	50
   min: 10	10	20	30	40	50
   min: 10	10	20	30	40	50
   Pass2	10	40	30	20	50
   min: 10	10	20	30	40	50
   min: 10	10	20	30	40	50
   min: 10	10	20	30	40	50
   Pass3	10	20	30	40	50
   min: 10	10	20	30	40	50
   min: 10	10	20	30	40	50
   Pass4	10	20	30	40	50
   min: 10	10	20	30	40	50

   • Even then, the complexity is \( O(n^{2}) \)
4. Properties
   
   • Selection sort uses only 1 swap per pass, so the number of swaps is minimized.
   • Selection sort is unstable.
   • The outer loop iterates through all the passes, and it runs for array.length-1 times.

11.1.3. Insertion Sort

public class Main {
    public static void insertionSort(int[] x){
        int temp, j;
        for(int i=1 ; i<x.length ; i++){
            temp = x[i];
            for(j = i-1 ; j>=0 && x[j]>temp ; j--)
                x[j+1] = x[j];
            x[j+1] = temp;
         
        }
    }
 
    public static void main(String[] args){
        int[] x = {489,99, 12, 25, 2, 343, 99};
        insertionSort(x);
        for(int i=0 ; i<x.length ; i++)
            System.out.print(x[i] + " ");
    }
}

1. Best Case
   

   \(O(n)\), as if the array is already sorted, then we won’t even enter the inner loop (x[j]>temp will be false)

2. Worst Case
   

   \(O(n^{2})\)

3. Properties
   
   • Stable
   • In place
   • You’d use this algorithm for a k-sorted array (elements are only ’k’ places away from their sorted positions.)

11.2.1. Quick Sort

1. Code
   

   public class Main {
       public static void quicksort(int[] x, int left, int right) {
           if (left < right) {
               int newRight = partition(x, left, right);
               quicksort(x, left, newRight - 1);
               quicksort(x, newRight + 1, right);
           }
       }
    
       public static int partition(int[] x, int left, int right) {
           int pivot = x[left];
           int i = left;
           int j = right;
        
           while (i < j) {
               while (i < right && x[i] <= pivot) i++;
               while (j > left && x[j] > pivot) j--;
               if (i < j)  swap(x, i, j);
           }
           swap(x, left, j);
           return j;
       }
    
       public static void swap(int[] ar, int i, int j) {
           int tmp = ar[i];
           ar[i] = ar[j];
           ar[j] = tmp;
       }
    
       public static void main(String[] args) {
           int[] x = {6, 1, 6, 6, 6, 5, 2, 6, 5, 1, 2, 6, 6, 3, 4, 6};
           quicksort(x, 0, x.length - 1);
           for (int i = 0; i < x.length; i++) {
               System.out.print(x[i] + " ");
           }
       }
   }
   

2. Best Case Complexity
   
   • The best case is when the pivot always divides the array equally throughout.
   • The complexity would be \(O(nlog(n))\)
3. Recurrence Relation
   

   \[ T(n) = 2T(\frac{n}{2}) + n \])

   • quickSort() is the recursive function, and inside that, a non-recursive function called partition() is being called.
   • That function has complexity \(O(n)\).
   • Hence the partition() function serves as the non-recursive part.
   • This, is assuming the best case
4. Worst Case Complexity
   
   • Quick Sort can have a complexity \(O(n^{2})\) when the array is completely sorted (ascending order or descending order)
5. Application of Quick Sort: Splitting numbers into 2 groups
   
   • In Quick Sort, every time we call the partition() method, we place the element in the place where it would be in the final sorted array.
   • Once we do that, everything to the left of that element would be smaller and everything to the right of that element would be larger. Do note that everything to the left aren’t themselves. They’re just smaller than the pivot. Similarly everything to the right are just larger than the pivot, and not necessarily sorted.
   • So in 1 call of the partition() method, we split the array into 2 groups:
     • Group 1: Everything smaller than the pivot (which lies to the left of the pivot)
     • Group 2: Everything larger than the pivot (which lies to the right of the pivot)
   • We can change this criteria of splitting numbers into 2 groups
   • For instance, if you take pivot = 0, and call partition() once, everything to the left of the pivot will be negative and everything to the right of the pivot will be positive. This is how you split positive and negative numbers.
6. Application of Quick Sort: Quick Select
   
   1. What it is
      
      • Quick Select is what we use to find the \(k^{th}\) smallest or largest element in any given array (doesn’t have to be sorted).
      • You keep partitioning and placing elements in their sorted positions by taking them as pivots one at a time.
      • In this process, if one of the pivots happen to be in index \(k\), you basically have the \(k^{th}\) element of the final sorted array, which is the \(k^{th}\) smallest element.
      • You’re not sorting the entire array, and then finding the \(k^{th}\) element in it. You’re gradually putting elements in their final sorted positions, and if one of those elements happen to be in position \(k\), we’ve found our element.
   2. Code
      

      public class Main {
          public static void main(String[] args) {
              int[] x = {6, 1, 6, 6, 6, 5, 2, 6, 5, 1, 2, 6, 6, 3, 4, 6};
              int k = 4; // Find the 4th smallest element (0-based index)
              int result = quickSelect(x, 0, x.length - 1, k);
              System.out.println("The " + (k + 1) + "th smallest element is: " + result);
          }
       
          static int quickSelect(int[]x , int left, int right, int k){
              if(left==right) return x[left];
              int newRight = partition(x, left, right);
              if(k < newRight)
                  return quickSelect(x, left, newRight-1, k);
              else if(newRight < k)
                  return quickSelect(x, newRight+1, right, k);
              else
                  return x[newRight];
          }
       
          static int partition(int[] x, int left, int right){
              int pivot = x[left];
              int i=left, j=right;
           
              while(i<j){
                  while(i<right && x[i]<=pivot) i++;
                  while(j>left && x[j]>pivot) j--;
               
                  if(i<j) swap(x, i, j);
              }
              swap(x, left, j);
              return j;
          }
       
          static void swap(int[] x, int i, int j){
              int temp = x[i];
              x[i] = x[j];
              x[j] = temp;
          }
      }
      
      

7. Application of Quick Sort: Quick Select to find an element occuring more than half the time in the array (and that element is the largest)
   

   public class Main {
       public static void main(String[] args) {
           int[] x = {6, 1, 6, 6, 6, 5, 2, 6, 5, 1, 2, 6, 6, 3, 4, 6};
           int n = x.length;
           int medianIndex = n / 2;
        
           // Step 1: Get the candidate at the median index using Quickselect
           int candidate = quickSelect(x.clone(), 0, n - 1, medianIndex);
        
           // Step 2: Count how many times it appears
           int count = 0;
           int max = Integer.MIN_VALUE;
           for (int num : x) {
               if (num == candidate) count++;
               if (num > max) max = num;
           }
        
           // Step 3: Check both conditions
           if (count > n / 2 && candidate == max) {
               System.out.println("x (majority max element) is: " + candidate);
           } else {
               System.out.println("No such 'x' exists.");
           }
       }
    
       static int quickSelect(int[] x, int left, int right, int k) {
           if (left == right) return x[left];
           int pivotIndex = partition(x, left, right);
        
           if (k < pivotIndex)
               return quickSelect(x, left, pivotIndex - 1, k);
           else if (k > pivotIndex)
               return quickSelect(x, pivotIndex + 1, right, k);
           else
               return x[pivotIndex];
       }
    
       static int partition(int[] x, int left, int right) {
           int pivot = x[left];
           int i = left, j = right;
        
           while (i < j) {
               while (i < right && x[i] <= pivot) i++;
               while (j > left && x[j] > pivot) j--;
               if (i < j) swap(x, i, j);
           }
           swap(x, left, j);
           return j;
       }
    
       static void swap(int[] x, int i, int j) {
           int temp = x[i];
           x[i] = x[j];
           x[j] = temp;
       }
   }
   
   

11.2.2. Merge Sort

1. Code
   

   public class Main {
    
       public static void main(String[] args){
           int[] x = {44, 33,5,  22, 10, 900};
           mergeSort(x);
           for(int i=0 ; i<x.length ; System.out.print(x[i++]+" "));
       }
       static void mergeSort(int[] x){
           if(x.length>1){ // There are more than 1 elements (only then can you split the array)
               int mid = (x.length)/2;
            
               int[] left = new int[mid]; // Has elements of indices 0, 1, 2, .. mid-1
               for(int i=0 ; i<mid ; left[i] = x[i++]);
            
               int[] right = new int[x.length - mid]; // Has elements of indices mid, mid + 1, ...x.length-1
               for(int i=mid ; i<x.length ; right[i-mid] = x[i++]);
            
               mergeSort(left);
               mergeSort(right);
               merge(x, left, right);
           }
       }
    
       static void merge(int[] x , int[] left , int[] right){
           int i, j, k;
        
           for(i=j=k=0 ; i<left.length && j<right.length ; k++){
               if(left[i]<right[j])
                   x[k] = left[i++];
               else
                   x[k] = right[j++];
           }
           while(i<left.length) x[k++] = left[i++];
           while(j<right.length) x[k++] = right[j++];
       }
   }
   
   

2. Application: Perfect use in Linked Lists
   
   • In this case, you don’t have to make 2 extra sub arrays.
   • You can manipulate the pointers and do everything in the same linked list.
   • Merge sort is one of the best sorting algorithms as it has time complexity \( O(nlogn) \). The main issue was that it needed extra space, and that is clearly eliminated in the case of Linked Lists.

11.2.3. Heap Sort

1. Array as a binary tree
   
   • An array is converted to a binary tree as follows:
     • Root node of the tree, is the element with index 0
     • From there, if the node of the heap is the element of index \(i\) in the array:
       • Left child = Element of index \(2i+1\)
       • Right child = Element of index \(2i+2\)

       • Parent of that node = Element of index \( \lfloor \frac{i}{2} \rfloor \)

         Source: geeksforgeeks

2. Some terminologies of Binary Trees
   
   1. Full Binary Tree: A binary tree with the maximum number of nodes possible for a given height.
      • If the height is \(h\), then the number of nodes present in the full binary tree is \(2^{h}-1\)

      • Eg. In the below example, \(h=4\). Number of nodes = \(2^{4}-1\) = \(15\) nodes (Last node will have index \(14\))

                              0
                           /    \
                        1          2
                      /  \       /   \
                    3     4     5     6
                  /  \  /  \   / \    / \
                7    8 9   10  11 12  13 14
        
        
        

   2. Complete Binary Tree: Except the lowest level, all other levels are completely filled, and the nodes at the lowest level are as left aligned as possible.

      • Eg.

        
                            0
                          /   \
                        1       2
                      /  \     /  \
                     3    4   5    6
                   /  \
                  7    8
        
        
        

      In the lowest level, if there is no node to the left of any node, then it’s not complete, because it’s not left-aligned. Here’s an example of a binary tree that’s not a complete binary tree:

      
                          0
                        /   \
                      1       2
                    /  \     /  \
                   3    4   5    6
                      /  \
                      7    8
      
      
      
      
      
      

   Here, there could have been a node to the left of node 7, but it’s vacant. Hence this is not a complete binary tree.

3. Property of a Complete Binary Tree
   

   If the number of nodes in a complete binary tree is \(n\), then the height of the tree is \(log_{2}(n+1)\).

4. Introduction to Heap
   
   1. Max Heap: A complete binary tree where any node is larger than its descendents.

   
   
   
           30
          /  \
        25    20
       /  \   /  \
     15   10 5    8
   
   
   
   
   

   1. Min Heap: A complete binary tree where any node is smaller than its descendents

           7
          / \
        12   15
       /  \  /  \
      18  30 25  40
   
   

5. How heaps can sort arrays
   
   • Here’s the basic idea:
     • Take all elements from the array one-by-one, and make a heap
     • Now delete all the elements from the heap and keep filling the original array from the end
   • In reality:
     • A heap graph is just a representation. All manipulation is done in the array itself
     • Making a heap is simply manipulating the existing array into an array which can be drawn like a heap. This is an inplace operation.
     • Deleting the elements from the heap and filling the original array, is where we swap the root element and the last unswapped element, and then we turn the rest of the unswapped elements back into a heap again.
6. Insertion and Deletion
   
   1. Insertion
      
      • When you insert into a heap, you always insert at the last index i.e. the node on the last level such that there are no gaps to the left.
      • Soon after this, you’ll have to keep comparing with the parents, and swapping to make the graph a max heap again
      • Inserting all of the elements of an array into a heap belongs to \(O(nlog(n))\)
   2. Deletion
      
      • When you delete from a heap, you always delete from the root
      • Again, you’ll keep comparing the children, and to maintain the max heap you’d swap with the largest child
      • nth deletion from the heap, fill the nth position of the array from the end
      • Deleting all elements from a heap belongs to \( O(nlog(n)) \)
      • You delete the root node, and the root node is the largest element of the heap. So deleting from a heap gives you the largest element.
7. How to Identify child nodes
   
   • Child nodes go from index number \( \lfloor \frac{n}{2} \rfloor \) to index number \(n-1\), where \(n\) is the number of elements in the heap/array
8. Heapify
   
   • You start from the last non-leaf node, which is index number \( \lfloor \frac{n}{2} \rfloor - 1 \)
   • Find the largest child (left or right) and if there is a child larger than the parent, swap the parent and that child
   • Now do the same thing assuming that largest child to be the new parent
9. Code
   

   public class Main {
       public static void main(String[] args){
           int[] x = {454,99, 3, 98, 10};
           HeapSort.heapSort(x);
           for(int i=0 ; i<x.length ; System.out.print(x[i++]+" "));
       }
    
   }
   
   class HeapSort {
       static void heapSort(int[] x){
           for(int i=(x.length/2)-1 ; i>=0 ; i--)
               heapify(x, x.length, i);
           for(int i=x.length-1 ; i>0 ; i--){
               int temp = x[0];
               x[0] = x[i];
               x[i] = temp;
               heapify(x, i, 0);
           }
       }
    
       static void heapify(int[] x , int n , int i){ // n: size of heap , i: node number
           int largest = i, left = 2*i + 1 , right = 2*i + 2;
        
           if(left<n && x[left]>x[largest]) largest = left;
           if(right<n && x[right]>x[largest]) largest = right;
        
           if(largest!=i){
               int temp = x[i];
               x[i] = x[largest];
               x[largest] = temp;
               heapify(x, n, largest);
           }
       }
   }
   
   

   • \(i\) is the node number, and it tells you from where you’re supposed to start heapification.
   • \(n\) (size of the heap), and it tells you where you’re supposed to stop heapification.
   • \( n = \text{(index of last element of heap)} + 1 \)

11.3.1. Counting Sort

1. Overview
   
   • Say the array given to us was A.
   • If you know the range of the elements present in the array (say the largest element is r), and r is way smaller than the size of the array, then this algorithm is useful.
   • Make an array c (stands for ’count’) of size r+1 (c[r+1]), and use this array to store the frequency of the elements (c[i] stores the frequency of the number i present in the array).
   • Turn this array into a cumulative frequency array.
   • c[i] now stores the last sorted position of the number i.
   • Go through the elements of the original array in reverse, and use that as an index of c and place the element in the new sorted array (yes you’ll have to make another array called sorted).
2. Code
   

   public class Main {
       public static void main(String[] args){
           int[] x = {45, 4, 9, 100, 69};
           countSort(x);
           for(int i=0 ; i<x.length ; System.out.print(x[i++]+" "));
       }
    
       static void countSort(int[] x){
           int r_index = 0;
           for(int i=0 ; i<x.length ; i++)
               if(x[r_index]<x[i])
                   r_index = i;
           int[] count = new int[x[r_index]+1];
        
           for(int i=0; i<x.length ; i++)
               count[x[i]]++;
            
           for(int i=1 ; i<count.length ; i++)
               count[i]+=count[i-1];
            
           int[] sorted = new int[x.length];
           for(int i=x.length-1 ; i>=0 ; i--){
               sorted[--count[x[i]]] = x[i];
           }
        
           for(int i=0 ; i<x.length ; x[i] = sorted[i++]);
       }
   }
   
   

3. Trivia
   
   • \( O(n+r) \), where \(r\) is the range of the elements.
   • If the range of the elements is comparable to the size of the array, then it just becomes \( O(n+n) \), which is basically \(O(2*n) \).
   • This algorithm is stable, only if you go through the elements of the original array in reverse.

11.3.2. Radix Sort

1. Code
   

   public class Main {
       public static void main(String[] args){
           int[] x = {45, 4, 9, 100, 69};
           countSortDig(x, 10);
           for(int i=0 ; i<x.length ; System.out.print(x[i++]+" "));
       }
    
       static void countSortDig(int[] x, int place){
       }
    
   }
   

12.1.1. What it is

12.1.2. Code

import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args){
        Set<String> x = new HashSet<>();
        x.add("Adithya");
        x.add("Varun");
        x.add("Manoj");
        x.add("Praanesh");
     
        x.remove("Praanesh");
     
        for(String i : x)
            System.out.println(i);
         
         
    }
}

Adithya
Varun
Manoj

12.3.1. Without Builtin Functions

public class Main {
    public static boolean hasDuplicate(int[] nums) {
        MyMap x = new MyMap(nums);
        for(int i=0 ; i<nums.length ; i++)
            if(x.hash[nums[i]-x.min_value]==0)
                x.hash[nums[i]-x.min_value] = 1;
            else
                return true;
        return false;
    }
    public static void main(String[] args){
        System.out.println(hasDuplicate(new int[]{2,2,7,8,5}));
    }
}

class MyMap {
    int[] hash;
    int min_value, max_value;
    MyMap(int[] nums) {
        this.max_value = nums[0];
        this.min_value = nums[0];
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]<this.min_value)
                this.min_value = nums[i];
            if(nums[i]>this.max_value)
                this.max_value = nums[i];
        }
        this.hash = new int[this.max_value-this.min_value+1];
    }
}

12.3.2. With Builtin functions

import java.util.Set;
import java.util.HashSet;

public class Main {
    public static boolean hasDuplicate(int[] nums) {
        Set<Integer> visited = new HashSet<>();
        for(int num : nums)
            if(visited.contains(num))
                return true;
            else
                visited.add(num);
        return false;
    }
    public static void main(String[] args){
        System.out.println(hasDuplicate(new int[]{2,3,7,8,5}));
    }
 
}

13.1.1. How it works

13.1.2. Complexity

13.3.1. What it is

13.3.2. Brute Force approach

max_sum = -9999999 # smallest integer ever
sum = -9999999 # smallest integer ever
for start in range(len(arr)):
    for end in range(start, len(arr)):
        for i in range(start, end):
            sum+=arr[i]
        if sum>max_sum:
            max_sum = sum
         
         

13.3.3. Brute Force, but slightly optimized

max_sum = -999999999 # (smallest integer ever)
sum = -99999999 # (smallest integer ever)
for start in range(len(arr)):
    sum = 0
    for end in range(len(arr)):
        sum+=arr[end]
        if sum>max_sum:
            max_sum = sum

13.3.4. Best approach

13.4.1. Prerequisite knowledge

1. Convex Polygon
   
   • A polygon with all interior angles less than 180 degrees
   • If you draw a line segment between any two points, the entire segment will lie inside the polygon.
2. Convex Hull
   
   • It’s the smallest convex polygon that surrounds all of the given points.
   • It’s simply represented as a set of points used to make that polygon.
3. Orientation of a point with respect to a line
   
   • https://dccg.upc.edu/people/vera/wp-content/uploads/2012/10/DAG-OrientationTests.pdf

13.4.2. What the problem statement is

13.4.3. How it works

1. Overview
   
   • Sort all of the points by their x-coordinates
   • Keep dividing them into 2 halves, until one part has only one point.
   • Calculate the convex hull for each subset
   • Merge the 2 convex hulls, into one big convex hull (recursively), by finding the upper and lower tangent between the two hulls
   • This is very similar to the approach used in merge sort.
     • Dividing them into 2 halves until they have one or two elements is almost exactly the same. In merge sort, an array of one element is already sorted and hence you can directly return that element. Here in convex hull, 1 or two points is already a convex hull. Hence you return it directly.
     • Calculating convex hull is like using mergeSort(left); and mergeSort(right);
     • Merging the 2 convex hulls is like merge(x, left, right);
   • So the entire logic is in the merge() function. In merge sort, you had to know how to merge two sorted arrays, into another sorted array. Here you need to know how to merge two convex hulls, into another convex hull.
2. Abstract idea of Merging
   
   • Say you already have the convex hull of the left half and the convex hull of the right half.
   • To make a convex hull out of these two, you need to connect them with an upper tangent and a lower tangent.
   • After finding the tangent, you need to remove the points in the interior of this figure, since you only need the outer most points.
3. How merging actually works
   
   • Before we move any further, you must know that after merging two convex hulls, the resultant convex hull will contain points arranged in a circular manner. This means that if you traverse across the array, you’ll either move along the convex hull in a clockwise direction, or an anti-clockwise direction.

13.5.1. What it is

13.5.2. Procedure

14.1.1. What it is

14.1.2. Procedure (Solved with an Example)

14.1.3. An Example where this can Fail

14.2.1. What it is

14.2.2. Procedure (Solved with an Example)

14.2.3. Code

import java.util.*;
public class Main {
    public static void main(String[] args){
        System.out.println(
              "Max Profit: " +
                      new Knapsack(
                            new int[]{4,8,2,6,1},
                            new int[]{12, 32, 40, 30, 50},
                            10
                      ).profit()
        );
    }
}
class Knapsack {
    int[] weights;
    int[] profits;
    int max_weight;
 
    Knapsack(int[] weights, int[] profits, int max_weight){
        this.weights = weights;
        this.profits = profits;
        this.max_weight = max_weight;
    }
 
    int profit(){
        int max_profit = 0;
        this.sort();
        int balance = this.max_weight;
        for(int i=0 ; i<this.weights.length ; i++)
            if(balance-this.weights[i]>=0){
                balance-= this.weights[i];
                max_profit+=profits[i];
            }
        return max_profit;
    }
 
 
    void sort(){
        for(int i=1 ; i<this.profits.length ; i++){
            int tempP = this.profits[i];
            int tempV = this.profits[i]/weights[i];
            int tempW = this.weights[i];
            int j;
            for(j=i-1 ; j>=0 && this.profits[j]/this.weights[j]<tempV ; j--){
                this.profits[j+1] = this.profits[j];
                this.weights[j+1] = this.weights[j];
            }
            this.profits[j+1] = tempP;
            this.weights[j+1] = tempW;
        }
    }
}

14.3.1. Code

public class Main {
    public static void main(String[] args){
        System.out.println(
              "Max Profit: " +
                      Knapsack(
                            new int[]{4,8,2,6,1},
                            new int[]{12, 32, 40, 30, 50},
                            10
                      )
        );
    }
    static double Knapsack(int[] weights, int[] profits, int max_weight){
        double max_profit = 0;
        int balance = max_weight;
        sort(weights, profits);
        for(int i=0 ; i<weights.length ; i++){
            if(balance-weights[i]>=0){
                balance-=weights[i];
                max_profit+=profits[i];
            }
            else{
                max_profit+=((double)profits[i]/weights[i])*balance;
                balance = 0;
            }
        }
     
        return max_profit;
    }
 
    static void sort(int[] weights, int[] profits){
        for(int i=1 ; i<profits.length ; i++){
            int tempWeight = weights[i], tempProfit = profits[i], j;
            for(j=i-1 ; j>=0 && (double)profits[j]/weights[j]<(double)tempProfit/tempWeight ; j--){
                weights[j+1] = weights[j];
                profits[j+1] = profits[j];
            }
            weights[j+1] = tempWeight;
            profits[j+1] = tempProfit;
        }
    }
}

14.4.1. What it is

14.4.2. Procedure (Solved with an Example)

14.4.3. Psuedocode

heap_sort(activities)
for i <= 1 to len(activities), do:
    if activities[i].start_time() < activities[i-1].end_time(), then:
        activity.remove(i)

14.5.1. What it is

14.5.2. Procedure (Solved with an Example)

14.6.1. What it is

14.6.2. Code

import java.util.*;

public class Main {
    public static void main(String[] args){
        System.out.println("Minimum Cost: "+ optimal_file_merge(new int[]{10, 20, 30, 40}));
    }
    static int optimal_file_merge(int[] sizes){
        PriorityQueue<Integer> x = new PriorityQueue<>();
        for(int i : sizes)
            x.add(i);
         
        int cost = 0, sum = 0;
        for(;x.size()>1;){
            sum = (x.poll() + x.poll());
            x.add(sum);
            cost+=sum;
        }
        return cost;
    }
}

14.7.1. What it is

15.1.1. Trivia

15.1.2. Code

import java.util.*;
public class Main {
    public static void main(String[] args){
        int n = 5;
        int[][] pascal_triangle = pascal(n);
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<n-i ; j++) System.out.print(" ");
            for(int j=0 ; j<=i ; j++)
                System.out.print(" "+pascal_triangle[i][j]+" ");
            System.out.println("");
        }
    }
 
    static int[][] pascal(int n){
        int[][] dp = new int[n+1][n+1];
        for(int i=0 ; i<n+1 ; i++) for(int j=0 ; j<=i ; j++)
                if(j==0 || i==j) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
        return dp;
    }
}

15.2.1. Trivia

15.2.2. DP Table

15.2.3. Code

import java.util.*;

public class Main {
    public static void main ( String [] args ) {
        int profit = knapsack(new int[]{4,8,2,6,1}, new int[]{12, 32, 40, 30, 50}, 10);
        System.out.println("Maximum Profit: " + profit);
    }
 
    public static int knapsack( int[] weight , int[] benefit , int maxWeight ) {
        int[][] DP = new int [weight.length +1][maxWeight +1];
        for ( int i = 0; i <= weight . length ; i ++)
            for ( int j = 0; j <= maxWeight ; j ++)
                if ( i == 0 || j == 0)
                    DP[i][j] = 0;
                else if ( weight [ i - 1] > j )
                    DP[i][j] = DP [ i - 1][ j ];
                else
                    DP[i][j] = Math.max(DP[i - 1][ j ], benefit[i - 1] + DP [i - 1][j - weight[i - 1]]);
        return DP[weight.length][maxWeight];
    }
 
}

15.3.1. Code to find minimum number of coins required to make an amount

import java.util.*;

public class Main {
    public static void main(String[] args){
        System.out.println("Minimum Number of Coins: "
                           + coinChange(
                                        new int[]{1,2,5},
                                        9
                             )
        );
     
    }
    public static int coinChange(int[] denomination, int maxWeight){
        int[][] DP = new int[denomination.length+1][maxWeight+1];
        for(int i=0 ; i < denomination.length+1 ; i++)
            for(int j=0 ; j < maxWeight+1 ; j++)
                if(j==0)
                    DP[i][j] = 0; // first column is 0
                else if(i==0)
                    DP[i][j] = java.lang.Integer.MAX_VALUE; // first row is the largest value possible
                else if( denomination[i-1] > j ) // the dp table has an extra 0 preceding. 'denomination[]' lacks that
                    DP[i][j] = DP[i-1][j];
                else
                    DP[i][j] = Math.min(
                                        DP[i-1][j],
                                        1 + DP[i][j-denomination[i-1]]
                               );
        return DP[denomination.length][maxWeight];
    }
}

15.3.2. Code to find Number of Ways to make an amount

// import java.util.*;

public class Main {
    public static void main(String[] args){
        System.out.println("Number of Ways: "
                           + numberOfWays(
                                        new int[]{1,2,5},
                                        9
                             )
        );
     
    }
    public static int numberOfWays(int[] denomination, int maxWeight){
        int[][] DP = new int[denomination.length+1][maxWeight+1];
        for(int i=0 ; i < denomination.length+1 ; i++)
            for(int j=0 ; j < maxWeight+1 ; j++)
                if(j==0)
                    DP[i][j] = 1; // first column is 1
                else if(i==0)
                    DP[i][j] = 0; // first row is 0
                else if(denomination[i-1] > j)
                    DP[i][j] = DP[i-1][j];
                else
                    DP[i][j] = DP[i-1][j] + DP[i][j-denomination[i-1]];
        return DP[denomination.length][maxWeight];
     
    }
}

15.4.1. What it is

15.4.2. Code

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> seq1 = Arrays.asList(1, 2, 3, 4, 1);
        List<Integer> seq2 = Arrays.asList(3, 4, 1, 2, 1, 3);
        List<Integer> lcs = LCS(seq1, seq2);
        for (int i = 0; i < lcs.size(); System.out.print(lcs.get(i++) + " "));
    }
 
    static List<Integer> LCS(List<Integer> seq1, List<Integer> seq2) {
        int m = seq1.size();
        int n = seq2.size();
     
        // Create a DP table to store lengths of LCS
        int[][] dp = new int[m + 1][n + 1];
     
        // Build the DP table
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else if (seq1.get(i - 1).equals(seq2.get(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
     
        // Now reconstruct the LCS from the DP table
        List<Integer> lcs = new ArrayList<>();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (seq1.get(i - 1).equals(seq2.get(j - 1))) {
                lcs.add(0, seq1.get(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
     
        return lcs;
    }
}

15.5.1. Code

import java.util.*;
public class Main {
    public static void main(String[] args){
        List<Integer> x = LIS(Arrays.asList(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15));
        for(int i=0 ; i<x.size() ; System.out.print(x.get(i++)+" "));
    }
    static List<Integer> LIS(List<Integer> seq){
        List<Integer> lis = new ArrayList<>();
     
        int[] dp = new int[seq.size()];
        for(int i=0 ; i<dp.length ; dp[i++] = 1);
     
        int[] previous_index = new int[seq.size()];
        for(int i=0 ; i<previous_index.length ; previous_index[i++] = -1);
     
        for(int i=0 ; i<seq.size() ; i++)
            for(int j=0 ; j<i ; j++)
                if(seq.get(i)>seq.get(j) && dp[i]<=dp[j]){
                    dp[i] = dp[j] + 1;
                    previous_index[i] = j;
                }
             
        int last_index = 0;
        for(int i=0 ; i<dp.length ; i++)
            if(dp[last_index]<dp[i]) last_index = i;
         
        for(; last_index>=0 ; last_index = previous_index[last_index])
            lis.add(0, seq.get(last_index));
         
         
        return lis;
    }
 
}

16.1.1. About Sudoku

16.1.2. Approach Taken

16.2.1. What it is

16.2.2. Code

16.3.1. What it is

16.3.2. Approach taken

16.4.1. What it is

16.4.2. Approach taken

16.6.1. What it is

16.6.2. Code

public class Main {
    public static void main(String[] args){
        int[] cycle = hamiltonian_cycle(
                        new int[][]{
                                {0, 1, 1, 0, 0},
                                {1, 0, 0, 1, 1},
                                {1, 0, 0, 1, 0},
                                {0, 1, 1, 0, 1},
                                {0, 1, 0, 1, 0}
                        }
                      );
        for(int i=0 ; i<cycle.length ; System.out.print(cycle[i++]+" "));
        System.out.print(cycle[0]);
     
    }
 
    static int[] hamiltonian_cycle(int[][] adjacency_matrix){
        int[] path = new int[adjacency_matrix.length];
        path[0] = 0;
        for(int i=1; i<path.length; path[i++]=-1);
        if (solve(adjacency_matrix, path, 1)) return path;
        return new int[0];
    }
 
    static boolean solve(int[][] matrix, int[] path, int pos) {
        if(pos == matrix.length)
            return matrix[path[matrix.length - 1]][path[0]] == 1;
        for(int i = 1; i < matrix.length; i++) {
            boolean in_path = false;
            for(int j=0; !in_path && j<pos; j++)
                if(path[j] == i)
                    in_path = true;
            if(!in_path && matrix[path[pos - 1]][i] == 1) {
                path[pos] = i;
                if(solve(matrix, path, pos + 1)) return true;
                path[pos] = -1;
            }
        }
        return false;
    }
}