Arrays in JAVA

An array is basically a bunch of elements of the same type, all stored together in one block of memory.

A Java array is like an object that holds elements of the same data type. The elements are stored next to each other in memory. It's a way to store similar items, but you can only put a fixed number of elements in a Java array.

Java arrays use indexes, so the first element is at index 0, the second at index 1, and so on.

Unlike C/C++, in Java, you can easily find out the length of an array using the length member. In C/C++, you'd have to use the sizeof operator.

In Java, an array is an object of a class that's created on the fly. Java arrays come from the Object class and implement the Serializable and Cloneable interfaces. They can hold either objects or primitive values. Just like in C/C++, you can create single or multi-dimensional arrays in Java.

Plus, Java has this cool feature called anonymous arrays, which you won't find in C/C++.

Advantages of Arrays in Java

1. Code Optimization

   • Enables efficient storage and retrieval of data.

   • Provides fast, low-level access to contiguous memory blocks.

   • Simplifies sorting and searching algorithms (e.g., binary search on sorted arrays).

2. Random Access

   • Direct access to any element via its index (e.g., arr[5]).

   • Constant-time complexity (O(1)) for read/write operations.

Disadvantages of Arrays in Java

1. Fixed Size

   • The length is set at creation and cannot be changed dynamically.

   • Requires manual resizing (e.g., copying to a new larger array), which is inefficient.

2. Memory Wastage

   • Over-provisioning (allocating more space than needed) wastes memory.

   • Under-provisioning (allocating less space) requires costly resizing.

3. No Built-in Methods

   • Lacks dynamic operations like add() or remove() (unlike ArrayList).

Comparison Table

When to Use Arrays?

• Ideal for static data (e.g., days of the week, chessboard).

• Best for performance-critical scenarios (e.g., mathematical computations).

When to Avoid Arrays?

• For dynamic data (use ArrayList or LinkedList instead).

• If frequent resizing is needed.

Types of Arrays in Java

1. Single-Dimensional Array (1D array)

2. Multidimensional Array (2D, 3D, etc.)

Single-Dimensional Arrays

A single-dimensional array is a linear collection of elements of the same data type, stored in contiguous memory locations.

Declaration Syntax

There are three valid ways to declare an array in Java:

dataType[] arr;    // Preferred style
dataType []arr;    // Valid but less common
dataType arr[];    // C-style (valid but not recommended in Java)

Instantiation

Arrays are objects in Java and must be instantiated using the new keyword:

arrayRefVar = new dataType[size];

Example Program

Here's a complete example demonstrating declaration, instantiation, initialization, and traversal:

// Java Program to demonstrate single-dimensional array operations
public class Main {
    public static void main(String args[]) {
        // Declaration and instantiation of an array
        int a[] = new int[5];

        // Initialization
        a[0] = 10;
        a[1] = 20;
        a[2] = 70;
        a[3] = 40;
        a[4] = 50;

        // Traversing array using for-loop
        for(int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

//o/p

10
20
70
40
50

Key Points:

1. Indexing: Java arrays are zero-indexed (first element is at index 0)

2. Length Property: The length property gives the size of the array

3. Default Values: Uninitialized array elements get default values (0 for numeric types, null for objects)

4. Memory Allocation: Arrays occupy contiguous memory blocks

Combined Declaration and Initialization

Arrays can be declared, instantiated, and initialized in one line:

int[] numbers = {10, 20, 30, 40, 50};  // No need to specify size explicitly

Common Operations

1. Accessing Elements: arrayName[index]

2. Modifying Elements: arrayName[index] = newValue

3. Finding Length: arrayName.length

4. Iterating: Using for-loop or for-each loop

Combined Array Operations in One Line

In Java, you can combine array declaration, instantiation, and initialization into a single concise statement:

dataType[] arrayName = {value1, value2, ..., valueN};

Example Code

// Java Program demonstrating combined array operations
public class Main {
    public static void main(String args[]) {
        // Combined declaration, instantiation and initialization
        int[] a = {33, 3, 4, 5};

        // Traversing array using for-loop
        for(int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

// o/p
33
3
4
5

Key Features of This Approach

1. Compact Syntax: Eliminates separate steps for declaration and initialization

2. Implicit Size Determination: The compiler automatically determines the array size

3. Readability: Makes code cleaner and more maintainable

Multidimensional Arrays

A multidimensional array is an array whose components are themselves arrays. The most common type is the two-dimensional (2D) array, which you can visualize as a table with rows and columns. However, Java supports arrays with even more dimensions (3D, 4D, etc.), though these are less commonly used.

Why Use Multidimensional Arrays?

Multidimensional arrays are invaluable when you need to:

• Represent matrices in mathematical computations

• Store game boards (like chess or tic-tac-toe)

• Handle image pixel data

• Manage spreadsheet-like data

• Work with 3D graphics coordinates

// Most common syntax for 2D arrays
dataType[][] arrayName;

// Alternative syntax (valid but less preferred)
dataType arrayName[][];  // or
dataType[] arrayName[];

For example, to declare a 2D integer array:

int[][] matrix;

Dimensions Explained

The number of bracket pairs indicates the number of dimensions:

• int[] - 1D array

• int[][] - 2D array

• int[][][] - 3D array

• And so on...

Creating Multidimensional Arrays

// 2D array with 3 rows and 4 columns
int[][] matrix = new int[3][4];

// 3D array (2x3x4)
int[][][] threeDArray = new int[2][3][4];

Ragged Arrays (Variable-Length Rows)

int[][] raggedArray = new int[3][]; // Only specify rows
raggedArray[0] = new int[2];       // First row has 2 columns
raggedArray[1] = new int[3];       // Second row has 3 columns
raggedArray[2] = new int[1];       // Third row has 1 column

Initializing Multidimensional Arrays

// 2D array initialization
int[][] matrix = {
    {1, 2, 3},  // First row
    {4, 5, 6},  // Second row
    {7, 8, 9}   // Third row
};

// Ragged array initialization
int[][] raggedArray = {
    {1, 2},
    {3, 4, 5},
    {6}
};

Dynamic Initialization

int size = 5;
char[][] board = new char[size][size];

// Initialize a checkerboard pattern
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
        board[i][j] = (i + j) % 2 == 0 ? 'X' : 'O';
    }
}

Accessing Array Elements

int[][] matrix = {{1, 2}, {3, 4}};

int firstElement = matrix[0][0];  // 1
int lastElement = matrix[1][1];   // 4

// Modify an element
matrix[0][1] = 10;  // Changes 2 to 10

ArrayIndexOutOfBoundsException

Be careful with indices - accessing beyond the array size throws an exception:

int value = matrix[2][0];  // Throws ArrayIndexOutOfBoundsException

Iterating Through Multidimensional Arrays

Nested For Loops

int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[i].length; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

Enhanced For Loop (For-Each)

for (int[] row : matrix) {
    for (int value : row) {
        System.out.print(value + " ");
    }
    System.out.println();
}

Using Arrays.deepToString()

For quick debugging, use Arrays.deepToString():

import java.util.Arrays;

System.out.println(Arrays.deepToString(matrix));
// Output: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Common Operations on Multidimensional Arrays

Matrix Addition

/**
 * Adds two matrices of the same dimensions and returns the result.
 * Matrix addition is performed element-wise (A + B = C where C[i][j] = A[i][j] + B[i][j]).
 * 
 * @param a The first matrix to add (2D array of integers)
 * @param b The second matrix to add (2D array of integers)
 * @return A new matrix containing the sum of a and b
 * @throws IllegalArgumentException if matrices have different dimensions
 */
public static int[][] addMatrices(int[][] a, int[][] b) {
    // Validate that matrices have the same dimensions
    // Check if number of rows are equal and if number of columns in first row are equal
    if (a.length != b.length || a[0].length != b[0].length) {
        throw new IllegalArgumentException("Matrices must have same dimensions");
    }

    // Create result matrix with same dimensions as input matrices
    int[][] result = new int[a.length][a[0].length];

    // Iterate through each element of the matrices
    for (int i = 0; i < a.length; i++) {          // Loop through rows
        for (int j = 0; j < a[i].length; j++) {   // Loop through columns
            // Add corresponding elements from both matrices
            result[i][j] = a[i][j] + b[i][j];
        }
    }

    // Return the resulting matrix
    return result;
}

Matrix Multiplication

/**
 * Multiplies two matrices and returns the resulting matrix.
 * Matrix multiplication requires that the number of columns in the first matrix (A) 
 * matches the number of rows in the second matrix (B). The resulting matrix will have
 * dimensions equal to the rows of A × columns of B.
 * 
 * The multiplication is performed using the standard matrix multiplication algorithm:
 * C[i][j] = Σ (A[i][k] * B[k][j]) for k = 0 to A's columns/B's rows
 * 
 * @param a The first matrix (2D array of integers)
 * @param b The second matrix (2D array of integers)
 * @return A new matrix containing the product of a and b
 * @throws IllegalArgumentException if the number of columns in 'a' doesn't match 
 *                                  the number of rows in 'b'
 */
public static int[][] multiplyMatrices(int[][] a, int[][] b) {
    // Get dimensions of input matrices
    int aRows = a.length;        // Number of rows in matrix A
    int aCols = a[0].length;     // Number of columns in matrix A
    int bRows = b.length;        // Number of rows in matrix B
    int bCols = b[0].length;     // Number of columns in matrix B

    // Validate that matrices can be multiplied
    // For matrix multiplication, columns of A must equal rows of B
    if (aCols != bRows) {
        throw new IllegalArgumentException(
            "Columns of first matrix must match rows of second matrix");
    }

    // Create result matrix with dimensions: aRows × bCols
    int[][] result = new int[aRows][bCols];

    // Perform matrix multiplication using triple nested loops
    for (int i = 0; i < aRows; i++) {         // Iterate through rows of A
        for (int j = 0; j < bCols; j++) {     // Iterate through columns of B
            // Calculate dot product of row i of A and column j of B
            for (int k = 0; k < aCols; k++) { // Iterate through columns of A/rows of B
                result[i][j] += a[i][k] * b[k][j];  // Multiply and accumulate
            }
        }
    }

    // Return the resulting matrix
    return result;
}

Transposing a Matrix

/**
 * Computes and returns the transpose of a given matrix.
 * The transpose of a matrix is obtained by flipping the matrix over its main diagonal,
 * switching the row and column indices of each element.
 * 
 * For example, the element at position [i][j] in the original matrix
 * will be at position [j][i] in the transposed matrix.
 * 
 * @param matrix The matrix to be transposed (2D array of integers)
 * @return A new matrix that is the transpose of the input matrix
 * @throws IllegalArgumentException if the input matrix is empty or null
 */
public static int[][] transpose(int[][] matrix) {
    // Check for null or empty matrix
    if (matrix == null || matrix.length == 0) {
        throw new IllegalArgumentException("Input matrix cannot be null or empty");
    }

    // Get dimensions of the original matrix
    int rows = matrix.length;     // Number of rows in original matrix
    int cols = matrix[0].length;  // Number of columns in original matrix

    // Create result matrix with inverted dimensions (cols × rows)
    int[][] result = new int[cols][rows];

    // Iterate through each element of the original matrix
    for (int i = 0; i < rows; i++) {          // Loop through rows
        for (int j = 0; j < cols; j++) {      // Loop through columns
            // Assign element [i][j] to [j][i] in the result
            result[j][i] = matrix[i][j];
        }
    }

    // Return the transposed matrix
    return result;
}

Memory Representation

Understanding how Java stores multidimensional arrays helps with performance optimization:

• Rectangular arrays: Contiguous memory blocks

• Ragged arrays: Arrays of references to other arrays

This affects:

• Cache locality

• Memory usage

• Access speed

Performance Considerations

1. Access Patterns: Accessing elements row-wise is generally faster due to how Java stores arrays in memory.

2. Bounds Checking: Java performs bounds checking on each array access, which adds a small overhead.

3. Object Overhead: Each array is an object, so ragged arrays have more overhead than rectangular ones.

How Arrays Work Internally in Java

An array in Java is a contiguous block of memory that stores elements of the same type.

Memory Representation

int[] arr = new int[5];

• Java allocates a fixed-size memory block (e.g., 5 * 4 bytes for int).

• Each element is stored sequentially in memory.

  Example:

    Memory Address | Value
    ---------------------
    1000          | arr[0] (default: 0)
    1004          | arr[1] (default: 0)
    1008          | arr[2] (default: 0)
    1012          | arr[3] (default: 0)
    1016          | arr[4] (default: 0)
  

How Indexing Works

• The memory address of arr[i] is calculated as:

    Base Address + (Index * Size_of_Element)
  

  • For arr[2] (assuming base = 1000, int = 4 bytes):

      1000 + (2 * 4) = 1008
    

  • This is why array access is O(1) (constant time).

Limitations

• Fixed size: Once created, the size cannot change.

• No bounds checking at compile time → ArrayIndexOutOfBoundsException at runtime.

ArrayList

In Java, an ArrayList is like a flexible version of an array. Unlike regular arrays that have a fixed size, an ArrayList can change size as you add or remove items. It's part of the Java Collections Framework and is super popular because it's so flexible and efficient.

Key Features of ArrayList

1. Dynamic Resizing: Automatically grows when elements are added beyond its capacity.

2. Index-Based Access: Allows fast random access using indices (like arrays).

3. Implements List Interface: Supports all List operations (add, remove, get, etc.).

4. Heterogeneous Elements (if not type-restricted): Can store different types if not using generics.

5. Not Synchronized: Not thread-safe by default (unlike Vector).

ArrayList vs. Array

How ArrayList Works Internally

1. Underlying Data Structure

• Internally uses an Object[] array to store elements.

• Default initial capacity = 10 (if not specified).

• When the array is full, it grows by ~50% (new capacity = old capacity * 1.5).

2. Key Internal Fields

private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData; // Actual storage
private int size; // Number of elements

3. Resizing Mechanism

When adding elements:

1. Checks if current capacity is sufficient.

2. If not, creates a new array with increased size.

3. Copies old elements to the new array (Arrays.copyOf).

Creating an ArrayList

1. Basic Declaration

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<>(); // Empty ArrayList
ArrayList<Integer> numbers = new ArrayList<>(20); // Initial capacity = 20

2. Initializing with Elements

ArrayList<String> fruits = new ArrayList<>(Arrays.asList("Apple", "Banana", "Orange"));

3. Using Collections

List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5));

Common ArrayList Operations

1. Adding Elements

ArrayList<String> list = new ArrayList<>();
list.add("Java"); // Appends to end
list.add(1, "Python"); // Inserts at index 1
list.addAll(Arrays.asList("C++", "JavaScript")); // Adds multiple elements

2. Accessing Elements

String first = list.get(0); // Gets element at index 0
int index = list.indexOf("Java"); // Returns first occurrence index (-1 if not found)
boolean exists = list.contains("Python"); // Checks existence

3. Removing Elements

list.remove(0); // Removes element at index 0
list.remove("Java"); // Removes first occurrence of "Java"
list.clear(); // Removes all elements

4. Updating Elements

list.set(0, "Kotlin"); // Replaces element at index 0

5. Iterating Over ArrayList

// For Loop
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// Enhanced For Loop
for (String item : list) {
    System.out.println(item);
}

// Using Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// Java 8+ forEach
list.forEach(System.out::println);

Performance Considerations

Best Practices

1. Specify Initial Capacity if size is known (reduces resizing overhead).

    ArrayList<Integer> list = new ArrayList<>(1000);
   

2. Use Generics for type safety.

    ArrayList<String> names = new ArrayList<>(); // ✅ Recommended
    ArrayList list = new ArrayList(); // ❌ Avoid (raw type)
   

3. Prefer isEmpty() over size() == 0 for readability.

4. Avoid Frequent add/remove in Middle (use LinkedList instead if needed).

5. Use Collections.synchronizedList for thread safety:

    List<String> syncList = Collections.synchronizedList(new ArrayList<>());
   

Use Cases

When to Use ArrayList:

• Frequent read operations (fast get()).

• Dynamic resizing needed.

• Sequential access (iterating).

When to Avoid ArrayList:

• Frequent insertions/deletions in the middle (use LinkedList).

• Thread safety required (use Vector or CopyOnWriteArrayList).

This is a lot of theory, so let's practice with some questions:

1. Linear Search

Steps to Perform Linear Search:

1. Start from index 0.
   Begin checking elements from the start of the array.

2. Compare each element with the target.

   • If nums[i] == target, return index i.

   • If not, move to the next element.

3. Repeat until the end of the array.

4. If you reach the end without finding the target, return -1.

// Given an array of integers nums and a target value, return the smallest index where the 
// target appears (0-based). If not found, return -1.

/**
 * This class demonstrates linear search implementation in Java.
 */
class Main {
    /**
     * Main method to test the linear search function.
     * @param args Command line arguments (not used)
     */
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // Test array

        // Test cases
        System.out.println(linearSearch(arr, 4)); // Should print 3 (index of 4)
        System.out.println(linearSearch(arr, 0)); // Should print -1 (not found)
    }

    /**
     * Performs linear search to find the target value in an array.
     * 
     * @param nums The array to search through
     * @param target The value to search for
     * @return The index of the target if found, -1 otherwise
     * 
     * Time Complexity: O(n) - Worst case scans entire array
     * Space Complexity: O(1) - Uses constant extra space
     */
    private static int linearSearch(int[] nums, int target) {
        // Iterate through each element in the array
        for (int i = 0; i < nums.length; i++) {
            // If current element matches target, return its index
            if (nums[i] == target) {
                return i;
            }
        }

        // Target not found in array
        return -1;
    }
}

// Space Complexity - O(1) as no extra space is used
// Time Complexity - O(n)  scans entire array

2. Largest Element

Method 1: Linear Search (Efficient Way)

Steps:

1. Start with a variable currentMax = Integer.MIN_VALUE.

2. Loop through each element of the array:

   • If nums[i] > currentMax, update currentMax.

3. After the loop ends, currentMax will have the maximum value.

Method 2: Sorting (Inefficient for this task)

Steps:

1. Check if array is null/empty → throw exception if true.

2. Sort the array using Arrays.sort(nums).

3. The last element nums[nums.length - 1] is the maximum.

// Given an array of integers nums, return the value of the largest element in the array
// Examples:
// Input: nums = [3, 3, 6, 1]
// Output: 6
// Explanation: The largest element in array is 6

/**
 * This class demonstrates finding the maximum value in an array using linear search.
 */
class Main {
    /**
     * Main method to test the max value finder function.
     * @param args Command line arguments (not used)
     */
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // Test array

        // Find and print the maximum value in the array
        System.out.println("Maximum value: " + findMax(arr)); // Expected output: 5
    }

    /**
     * Finds the maximum value in an integer array.
     * 
     * @param nums The array to search through (must not be null or empty)
     * @return The maximum value found in the array
     * @throws IllegalArgumentException if the input array is null or empty
     * 
     * Time Complexity: O(n) - Must examine every element in worst case
     * Space Complexity: O(1) - Uses constant extra space
     */
    private static int findMax(int[] nums) {
        // Validate input array
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array cannot be null or empty");
        }

        // Initialize with smallest possible integer value
        int currentMax = Integer.MIN_VALUE;

        // Iterate through each element
        for (int i = 0; i < nums.length; i++) {
            // Update currentMax if we find a larger value
            if (nums[i] > currentMax) {
                currentMax = nums[i];
            }
        }

        return currentMax;
    }
}

// method 2 

import java.util.Arrays;

/**
 * This class demonstrates finding the maximum value in an array using sorting.
 * Note: This approach is less efficient for simply finding the max value compared to
   linear search.
 */
class Main {
    /**
     * Main method to test the maximum value finder function.
     * @param args Command line arguments (not used)
     */
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // Test array

        // Find and print the maximum value in the array
        System.out.println("Maximum value: " + findMaxBySorting(arr)); // Expected output: 5
    }

    /**
     * Finds the maximum value by sorting the array and returning the last element.
     * 
     * @param nums The array to process (must not be null or empty)
     * @return The maximum value in the array
     * @throws IllegalArgumentException if the input array is null or empty
     * 
     * Time Complexity: O(n log n) - Due to sorting operation
     * Space Complexity: O(1) - If sorting is done in-place
     * 
     * Note: While this works, it's inefficient for just finding the max value.
     * A linear search (O(n)) would be more efficient for this specific task.
     */
    private static int findMaxBySorting(int[] nums) {
        // Validate input array
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array cannot be null or empty");
        }

        // Sort the array in ascending order
        Arrays.sort(nums);

        // The maximum value will be the last element after sorting
        return nums[nums.length - 1];
    }
}

3. Second Largest Element

Method 1: Single-Pass Efficient Approach

• Use two variables:

  • max – to store the largest element

  • secondMax – to store the second-largest element

• Traverse the array:

  • If current number > max → update secondMax = max, and max = num

  • Else if current number > secondMax and not equal to max → update secondMax = num

• If secondMax is still Integer.MIN_VALUE after the loop, return -1.

Method 2: Sorting Approach

• Sort the array in ascending order

• Traverse backward to find the first element smaller than the last one (i.e., the max)

Summary Table:

// Given an array of integers nums, return the second-largest element in the array. If the second-largest element does not exist, return -1.
// Examples:
// Input: nums = [8, 8, 7, 6, 5]
// Output: 7
// Explanation: The largest value in nums is 8, the second largest is 7

import java.util.Arrays;

/**
 * This class demonstrates different methods to find the second largest element in an array.
 */
class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // Test array

        // Find and print the second largest value
        System.out.println("Second largest value: " + findSecondLargest(arr));
    }

    /**
     * Finds the second largest element in an array using two approaches.
     * 
     * @param nums The input array (must contain at least 2 distinct elements)
     * @return The second largest element in the array
     * @throws IllegalArgumentException if array has less than 2 elements
     */
    private static int findSecondLargest(int[] nums) {
        // Input validation
        if (nums == null || nums.length < 2) {
            throw new IllegalArgumentException("Array must contain at least 2 elements");
        }

        // METHOD 1: Single pass approach (O(n) time, O(1) space)
        int max = Integer.MIN_VALUE;
        int secondMax = Integer.MIN_VALUE;

        for (int num : nums) {
            if (num > max) {
                secondMax = max;  // Current max becomes second max
                max = num;        // Update max with new value
            } 
            else if (num > secondMax && num != max) {
                secondMax = num;   // Update second max
            }
        }

        // Handle case where all elements are same
        if (secondMax == Integer.MIN_VALUE) {
            throw new IllegalArgumentException("All elements are identical");
        }

        return secondMax;


        // METHOD 2: Sorting approach (O(n log n) time, O(1) space if sorted in-place)
        Arrays.sort(nums);

        // Handle duplicates by finding first distinct element from end
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] != nums[nums.length - 1]) {
                return nums[i];
            }
        }

        throw new IllegalArgumentException("All elements are identical");

    }
}

4. Maximum Consecutive Ones

Method : Single-Pass Efficient Approach

• Use two variables:

  • maxCount: stores the overall maximum count of 1s.

  • currentCount: counts the ongoing sequence of 1s.

• Traverse through the array:

  • If the number is 1, increment currentCount and update maxCount if currentCount is larger.

  • If the number is 0, reset currentCount to 0.

• Return maxCount.

// Given a binary array nums, return the maximum number of consecutive 1s in the array.
// A binary array is an array that contains only 0s and 1s.
// Examples:
// Input: nums = [1, 1, 0, 0, 1, 1, 1, 0]
// Output: 3
// Explanation: The maximum consecutive 1s are present from index 4 to index 6, amounting to 3 1s

/**
 * This class calculates the maximum number of consecutive 1's in a binary array.
 */
class Main {
    public static void main(String[] args) {
        int[] arr = {1,1,1,0,0,1,0,1,1,1,1,1,0,0,0}; // Test array

        System.out.println("Maximum consecutive 1's: " + maxConsecutiveOnes(arr));
        // Expected output: 5 (sequence of five 1's at the end)
    }

    /**
     * Finds the maximum number of consecutive 1's in a binary array.
     * 
     * @param nums Binary array containing only 0's and 1's
     * @return Maximum count of consecutive 1's
     * @throws IllegalArgumentException if input array is null
     * 
     * Time Complexity: O(n) - Single pass through the array
     * Space Complexity: O(1) - Uses constant extra space
     */
    private static int maxConsecutiveOnes(int[] nums) {
        // Input validation
        if (nums == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }

        int maxCount = 0;    // Tracks maximum consecutive 1's found
        int currentCount = 0; // Counts current streak of consecutive 1's

        for (int num : nums) {
            if (num == 1) {
                currentCount++;  // Increment current streak
                maxCount = Math.max(maxCount, currentCount); // Update max if needed
            } 
            else if (num == 0) {
                currentCount = 0; // Reset current streak
            }
            // Note: Ignores any values that aren't 0 or 1
        }

        return maxCount;
    }
}

5. Left Rotate Array by One

Method : In-Place Shift (Efficient & Simple)

• Store the first element in a temporary variable.

• Shift all elements to the left by one position.

• Place the original first element at the last index.

// Given an integer array nums, rotate the array to the left by one.
// Note: There is no need to return anything, just modify the given array.
// Examples:
// Input: nums = [1, 2, 3, 4, 5]
// Output: [2, 3, 4, 5, 1]
// Explanation: Initially, nums = [1, 2, 3, 4, 5]
// Rotating once to left -> nums = [2, 3, 4, 5, 1]

/**
 * This class demonstrates left rotation of an array by one position.
 */
class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // Test array

        System.out.println("Original array: " + Arrays.toString(arr));
        int[] rotated = leftRotateByOne(arr);
        System.out.println("After rotation: " + Arrays.toString(rotated));
        /* Expected Output:
           Original array: [1, 2, 3, 4, 5]
           After rotation: [2, 3, 4, 5, 1]
        */
    }

    /**
     * Performs a left rotation on the array by one position.
     * 
     * @param nums The array to rotate (must not be null or empty)
     * @return The rotated array
     * @throws IllegalArgumentException if input array is null or empty
     * 
     * Time Complexity: O(n) - Single pass through array
     * Space Complexity: O(1) - In-place rotation with constant extra space
     */
    private static int[] leftRotateByOne(int[] nums) {
        // Input validation
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array cannot be null or empty");
        }

        // Store first element to move to end later
        int firstElement = nums[0];

        // Shift all elements left by one position
        for (int i = 0; i < nums.length - 1; i++) {
            nums[i] = nums[i + 1];
        }

        // Move original first element to last position
        nums[nums.length - 1] = firstElement;

        return nums;
    }
}

6. Left Rotate Array by K Places

Method 1 : Using Temporary Array

• If k is larger than array length, take k = k % length to avoid unnecessary rotations.

• Store the first k elements temporarily.

• Shift the rest of the elements in the array left by k positions.

• Copy the stored elements back to the end of the array.

Method 2 : Reversal Algorithm

1. Normalize k by taking k % n to handle cases where k > length of array.

2. Reverse the entire array.

3. Reverse the first k elements.

4. Reverse the remaining n - k elements.

Summary Table:

// Given an integer array nums and a non-negative integer k, rotate the array to the left by k steps.
// Examples:
// Input: nums = [1, 2, 3, 4, 5, 6], k = 2
// Output: nums = [3, 4, 5, 6, 1, 2]
// Explanation: rotate 1 step to the left: [2, 3, 4, 5, 6, 1]
// rotate 2 steps to the left: [3, 4, 5, 6, 1, 2]

import java.util.Arrays;

/**
 * This class demonstrates left rotation of an array by K positions.
 */
class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // Test array
        int k = 3; // Rotation count

        System.out.println("Original array: " + Arrays.toString(arr));
        int[] rotated = leftRotateByK(arr, k);
        System.out.println("After rotating left by " + k + " positions: " + Arrays.toString(rotated));
        /* Expected Output:
           Original array: [1, 2, 3, 4, 5]
           After rotating left by 3 positions: [4, 5, 1, 2, 3]
        */
    }

    /**
     * Performs a left rotation on the array by K positions.
     * 
     * @param nums The array to rotate (must not be null)
     * @param k The number of positions to rotate (should be non-negative)
     * @return The rotated array
     * @throws IllegalArgumentException if input array is null or k is negative
     * 
     * Time Complexity: O(n) - Three passes through array
     * Space Complexity: O(k) - Additional space for storing first K elements
     */
    private static int[] leftRotateByK(int[] nums, int k) {
        // Input validation
        if (nums == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }
        if (k < 0) {
            throw new IllegalArgumentException("Rotation count cannot be negative");
        }

        // Handle case where k is larger than array length
        k = k % nums.length;
        if (k == 0) {
            return nums.clone(); // No rotation needed
        }

        // 1. Store first K elements in temporary array
        int[] firstKElements = Arrays.copyOfRange(nums, 0, k);

        // 2. Shift remaining elements to the left
        System.arraycopy(nums, k, nums, 0, nums.length - k);

        // 3. Append stored elements to the end
        System.arraycopy(firstKElements, 0, nums, nums.length - k, k);

        return nums;
    }
}

import java.util.Arrays;

/**
 * This class demonstrates array rotation using the reversal algorithm.
 * This approach rotates the array in O(n) time with O(1) space complexity.
 */
class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5}; // Original array
        int k = 2; // Number of positions to rotate right

        System.out.println("Original array: " + Arrays.toString(nums));

        rotateRight(nums, k);

        System.out.println("After rotating right by " + k + " positions: " + Arrays.toString(nums));
        /* Expected Output:
           Original array: [1, 2, 3, 4, 5]
           After rotating right by 2 positions: [4, 5, 1, 2, 3]
        */
    }

    /**
     * Rotates the array to the right by k positions using reversal algorithm.
     * 
     * @param nums The array to rotate (must not be null)
     * @param k The number of positions to rotate (non-negative)
     * 
     * Time Complexity: O(n) - Each element is moved twice
     * Space Complexity: O(1) - In-place rotation
     */
    public static void rotateRight(int[] nums, int k) {
        // Input validation
        if (nums == null) {
            throw new IllegalArgumentException("Input array cannot be null");
        }
        if (k < 0) {
            throw new IllegalArgumentException("Rotation count cannot be negative");
        }

        int n = nums.length;
        if (n == 0) return; // No rotation needed for empty array

        // Normalize k to be within array bounds
        k = k % n;
        if (k == 0) return; // No rotation needed

        // Step 1: Reverse the entire array
        reverse(nums, 0, n - 1);

        // Step 2: Reverse the first k elements
        reverse(nums, 0, k - 1);

        // Step 3: Reverse the remaining n-k elements
        reverse(nums, k, n - 1);
    }

    /**
     * Reverses elements in the array between indices start and end (inclusive).
     * 
     * @param nums The array to modify
     * @param start The starting index (inclusive)
     * @param end The ending index (inclusive)
     */
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            // Swap elements at start and end indices
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            // Move indices towards center
            start++;
            end--;
        }
    }
}

7. Move Zeros to End

Method 1: Bubble-Swap (Naive)

• Iterate through the array.

• Whenever a zero is found, swap it with the next non-zero element.

• This results in pushing zeros toward the end.

• However, this uses nested loops resulting in higher time complexity.

Method 2: Optimized Two-Pass

• Maintain a pointer count to track the position for placing non-zero elements.

• First pass: Copy all non-zero elements forward.

• Second pass: Fill the remaining positions with zeros.

Summary Table:

// Given an integer array nums, move all the 0's to the end of the array. The relative order of the other elements must remain the same. This must be done in place, without making a copy of the array.
// Examples:
// Input: nums = [0, 1, 4, 0, 5, 2]
// Output: [1, 4, 5, 2, 0, 0]
// Explanation: Both the zeroes are moved to the end and the order of the other elements stay the same

import java.util.Arrays;

/**
 * This class demonstrates moving zeros to the end of an array using two different approaches.
 */
class ZeroMover {
    public static void main(String[] args) {
        int[] nums = {0, 1, 4, 0, 5, 2};

        System.out.println("Original array: " + Arrays.toString(nums));
        System.out.println("Bubble-swap result: " + 
            Arrays.toString(moveZerosBubbleSwap(nums.clone())));
    }

    /**
     * Moves zeros to the end using bubble-swap approach (not optimal)
     * 
     * @param nums The array to process (will be modified)
     * @return The modified array with zeros at the end
     * 
     * Time Complexity: O(n²) - Nested loops
     * Space Complexity: O(1) - In-place modification
     */
    private static int[] moveZerosBubbleSwap(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == 0) {
                    swap(nums, i, j);
                }
            }
        }
        return nums;
    }

    /**
     * Swaps two elements in an array
     * 
     * @param nums The array containing elements to swap
     * @param i First index
     * @param j Second index
     * @return The array with swapped elements
     */
    private static int[] swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        return nums;
    }
}

/**
 * Optimized version for moving zeros to the end
 */
class ZeroMoverOptimized {
    public static void main(String[] args) {
        int[] nums = {0, 1, 4, 0, 5, 2};

        System.out.println("Original array: " + Arrays.toString(nums));
        System.out.println("Optimized result: " + 
            Arrays.toString(moveZerosOptimized(nums.clone())));
    }

    /**
     * Moves zeros to the end in O(n) time
     * 
     * @param nums The array to process (will be modified)
     * @return The modified array with zeros at the end
     * 
     * Time Complexity: O(n) - Two passes through array
     * Space Complexity: O(1) - In-place modification
     */
    private static int[] moveZerosOptimized(int[] nums) {
        int count = 0; // Tracks position for non-zero elements

        // First pass: Move all non-zero elements to front
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[count++] = nums[i];
            }
        }

        // Second pass: Fill remaining positions with zeros
        while (count < nums.length) {
            nums[count++] = 0;
        }

        return nums;
    }
}

8. Remove duplicates from sorted array

Method 1: Using HashSet (for unsorted arrays)

Logic:

• A HashSet automatically ignores duplicates.

• Traverse the array and insert each element into the set.

• Convert the set back to an array.

Method 2: Two-Pointer Technique (Optimized for Sorted Arrays)

Logic:

• Use a slow pointer (unique) to track the last unique element.

• Use a fast pointer (i) to scan the array.

• When a new unique element is found, update the unique + 1 position.

• Finally, return a copy of the array up to the last unique index.

Summary Table:

---

// Given an integer array nums sorted in non-decreasing order, remove all duplicates in-place so that each unique element appears only once. Return the number of unique elements in the array.

// If the number of unique elements be k, then,
// Change the array nums such that the first k elements of nums contain the unique values in the order that they were present originally.
// The remaining elements, as well as the size of the array does not matter in terms of correctness.

// An array sorted in non-decreasing order is an array where every element to the right of an element is either equal to or greater in value than that element.
// Examples:
// Input: nums = [0, 0, 3, 3, 5, 6]
//Output: 4
//Explanation: Resulting array = [0, 3, 5, 6, _, _]
// There are 4 distinct elements in nums and the elements marked as _ can have any value.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Input array with duplicates
        int[] arr = {0, 0, 3, 3, 5, 6};

        // Call removeDuplicates and print the result
        System.out.println(Arrays.toString(removeDuplicates(arr)));
    }

    /**
     * Removes duplicate elements from an integer array.
     * @param arr The input array (may contain duplicates)
     * @return A new array containing only unique elements
     */
    private static int[] removeDuplicates(int[] arr) {
        // Create a HashSet to store unique elements
        // HashSet automatically handles duplicates by storing only unique values
        Set<Integer> temp = new HashSet<>(); 

        // Iterate through the input array and add elements to the set
        // Duplicates will be automatically ignored
        for(int i = 0; i < arr.length; i++) {
            temp.add(arr[i]);
        }

        // Create a new array with size equal to the number of unique elements
        int[] result = new int[temp.size()];

        // Copy elements from the set to the result array
        int i = 0;
        for (int num : temp) {
            result[i++] = num;
        }

        // Return the array containing unique elements
        return result;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Input array (sorted with duplicates)
        int[] arr = {0, 0, 3, 3, 5, 6};
        // Print the array after removing duplicates
        System.out.println(Arrays.toString(removeDuplicates(arr)));
    }

    /**
     * Removes duplicates from a sorted array in-place using the two-pointer technique.
     * 
     * @param arr The input sorted array (may contain duplicates)
     * @return A new array with duplicates removed
     * 
     * Time Complexity: O(n) – Single pass through the array
     * Space Complexity: O(1) – Operates in-place (no extra space used)
     */
    private static int[] removeDuplicates(int[] arr) {
        // Edge case: empty array
        if (arr.length == 0) {
            return arr;
        }

        // Pointer to track the position of the last unique element
        int unique = 0;

        // Iterate through the array starting from the second element
        for (int i = 1; i < arr.length; i++) {
            // If current element is different from the last unique element
            if (arr[i] != arr[unique]) {
                // Move the unique pointer forward and update with the new unique element
                arr[++unique] = arr[i];
            }
            // Else: skip the duplicate (do nothing)
        }

        // Return a copy of the array up to the last unique element
        return Arrays.copyOf(arr, unique + 1);
    }
}

9. Find missing number

Method 1: Sorting + Linear Search

Logic

• Sort the array.

• The first index where nums[i] != i is the missing number.

• If all indices match, the missing number is n.

Method 2: Math Formula (Gauss’ Trick)

Logic

• The sum of first n numbers is n*(n+1)/2.

• Subtract the sum of the array to find the missing number.

Method 3: XOR Bit Manipulation (Most Optimal)

Logic

• XOR all numbers from 1 to n → xor1.

• XOR all elements in the array → xor2.

• XOR of xor1 ^ xor2 gives the missing number (since all duplicates cancel out).

Summary Table:

// Given an integer array of size n containing distinct values in the range from 0 to n (inclusive), return the only number missing from the array within this range.
// Examples:
// Input: nums = [0, 2, 3, 1, 4]
// Output: 5
// Explanation: nums contains 0, 1, 2, 3, 4 thus leaving 5 as the only missing number in the range [0, 5]

import java.util.Arrays;

class Solution {
    /**
     * Finds the missing number in an array containing [0, n] where one number is missing.
     * 
     * @param nums Input array with n distinct numbers in [0, n] (missing one number)
     * @return The missing number
     */
    public int missingNumber(int[] nums) {
        // Method 1: Sorting + Linear Search
        // Time: O(n log n), Space: O(1) (modifies input)
        // ----------------------------------------------
        // Arrays.sort(nums);  // Sort the array
        // for (int i = 0; i < nums.length; i++) {
        //     // The first index where nums[i] != i is the missing number
        //     if (nums[i] != i) {
        //         return i;
        //     }
        // }
        // // If all indices match, the missing number is 'n' (last element)
        // return nums.length;

        // Method 2: Mathematical Sum Formula (Gauss' Trick)
        // Time: O(n), Space: O(1)
        // ----------------------------------------------
        // int n = nums.length;
        // int expectedSum = (n * (n + 1)) / 2;  // Sum of [0, n]
        // int actualSum = 0;
        // for (int num : nums) {
        //     actualSum += num;  // Sum of array elements
        // }
        // // Missing number = expected sum - actual sum
        // return expectedSum - actualSum;

        // Method 3: XOR Bit Manipulation (Optimal)
        // Time: O(n), Space: O(1)
        // ----------------------------------------------
        int xor1 = 0;  // XOR of all numbers from 1 to n
        int xor2 = 0;  // XOR of all array elements

        for (int i = 0; i < nums.length; i++) {
            xor1 ^= (i + 1);  // XOR with [1...n]
            xor2 ^= nums[i];  // XOR with array elements
        }

        // The missing number is the XOR of the two results
        // (since XOR cancels out all existing numbers)
        return xor1 ^ xor2;
    }
}

10. Union of two sorted arrays

Method 1: Two-Pointer Merge (for Sorted Arrays)

Logic

• Use two pointers i and j to walk through both arrays.

• At each step, compare elements:

  • Add the smaller one (if not already added).

  • If equal, add one of them (to avoid duplicates) and move both pointers.

• After one array finishes, process the remaining elements of the other array.

Method 2: TreeSet (for Any Arrays)

Logic

• Use a TreeSet to store unique elements automatically in sorted order.

• Add all elements from both arrays to the set.

Summary Table:

---

// Given two sorted arrays nums1 and nums2, return an array that contains the union of these two arrays. The elements in the union must be in ascending order.
// The union of two arrays is an array where all values are distinct and are present in either the first array, the second array, or both.
// Examples:
// Input: nums1 = [1, 2, 3, 4, 5], nums2 = [1, 2, 7]
// Output: [1, 2, 3, 4, 5, 7]
//Explanation: The elements 1, 2 are common to both, 3, 4, 5 are from nums1 and 7 is from nums2

class Solution {
    /**
     * Finds the union of two sorted arrays using a two-pointer approach.
     * 
     * @param nums1 First sorted array (may contain duplicates)
     * @param nums2 Second sorted array (may contain duplicates)
     * @return Union of both arrays as a sorted array without duplicates
     * 
     * Time Complexity: O(n + m), where n = nums1.length, m = nums2.length
     * Space Complexity: O(n + m) for the result list
     */
    public int[] unionArray(int[] nums1, int[] nums2) {
        List<Integer> unionList = new ArrayList<>();
        int i = 0, j = 0;
        int n = nums1.length;
        int m = nums2.length;

        // Merge process similar to merge sort
        while (i < n && j < m) {
            // Case when nums1[i] is smaller or equal
            if (nums1[i] <= nums2[j]) {
                // Add to union if it's not a duplicate
                if (unionList.isEmpty() || unionList.get(unionList.size() - 1) != nums1[i]) {
                    unionList.add(nums1[i]);
                }
                i++;
            } 
            // Case when nums2[j] is smaller
            else {
                // Add to union if it's not a duplicate
                if (unionList.isEmpty() || unionList.get(unionList.size() - 1) != nums2[j]) {
                    unionList.add(nums2[j]);
                }
                j++;
            }
        }

        // Add remaining elements from nums1
        while (i < n) {
            if (unionList.isEmpty() || unionList.get(unionList.size() - 1) != nums1[i]) {
                unionList.add(nums1[i]);
            }
            i++;
        }

        // Add remaining elements from nums2
        while (j < m) {
            if (unionList.isEmpty() || unionList.get(unionList.size() - 1) != nums2[j]) {
                unionList.add(nums2[j]);
            }
            j++;
        }

        // Convert List<Integer> to int[]
        int[] union = new int[unionList.size()];
        for (int k = 0; k < unionList.size(); k++) {
            union[k] = unionList.get(k);
        }

        return union;
    }
}

class Solution {
    /**
     * Finds the union of two arrays using a TreeSet (works for unsorted arrays).
     * 
     * @param nums1 First array (may be unsorted and contain duplicates)
     * @param nums2 Second array (may be unsorted and contain duplicates)
     * @return Union of both arrays as a sorted array without duplicates
     * 
     * Time Complexity: O((n + m) log (n + m)) due to TreeSet operations
     * Space Complexity: O(n + m) for the TreeSet
     */
    public int[] unionArray(int[] nums1, int[] nums2) {
        // TreeSet automatically sorts and removes duplicates
        Set<Integer> set = new TreeSet<>();

        // Add all elements from both arrays to the set
        for (int num : nums1) {
            set.add(num);  // O(log n) per insertion
        }

        for (int num : nums2) {
            set.add(num);  // O(log m) per insertion
        }

        // Convert set to int[]
        int[] result = new int[set.size()];
        int i = 0;
        for (int num : set) {
            result[i++] = num;
        }

        return result;
    }
}

11. Intersection of two sorted arrays

Method 1: Two-Pointer Technique (For Sorted Arrays)

Logic

• Use two pointers i and j to traverse both arrays.

• If elements at both pointers are equal, add to result and move both.

• If not equal, move the pointer from the array with the smaller value.

• This ensures no extra comparisons and preserves count-based intersection.

Method 2: HashMap (For Unsorted Arrays or Counting)

Logic

• Use a HashMap to store the count of elements in nums1.

• Iterate through nums2 and check if that element exists in the map with a positive count.

• If yes, add to result and decrement count.

Summary Table:

---

// Given two sorted arrays, nums1 and nums2, return an array containing the intersection of these two arrays. Each element in the result must appear as many times as it appears in both arrays.
// The intersection of two arrays is an array where all values are present in both arrays.
// Examples:
// Input: nums1 = [1, 2, 2, 3, 5], nums2 = [1, 2, 7]
// Output: [1, 2]
// Explanation: The elements 1, 2 are the only elements present in both nums1 and nums2

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Input arrays (should be sorted for this algorithm to work correctly)
        int[] arr1 = {1, 2, 2, 3, 5};  // First sorted array with duplicates
        int[] arr2 = {1, 2, 7};         // Second sorted array

        // Find and print the intersection of the two arrays
        System.out.print(Arrays.toString(intersection(arr1, arr2)));
    }

    /**
     * Finds the intersection of two sorted arrays.
     * 
     * @param nums1 First sorted array (may contain duplicates)
     * @param nums2 Second sorted array (may contain duplicates)
     * @return Array containing common elements between nums1 and nums2
     * 
     * Time Complexity: O(n + m), where n = nums1.length, m = nums2.length
     * Space Complexity: O(min(n, m)) for storing the result
     */
    private static int[] intersection(int[] nums1, int[] nums2) {
        // List to store the intersection elements
        List<Integer> tempList = new ArrayList<>();

        // Initialize pointers for both arrays
        int i = 0;  // Pointer for nums1
        int j = 0;  // Pointer for nums2
        int n = nums1.length;
        int m = nums2.length;

        // Traverse both arrays using two-pointer technique
        while (i < n && j < m) {
            // Case 1: Elements are equal (found intersection)
            if (nums1[i] == nums2[j]) {
                tempList.add(nums1[i]);  // Add to result
                i++;  // Move both pointers
                j++;
            }
            // Case 2: nums1 element is larger
            else if (nums1[i] > nums2[j]) {
                j++;  // Move nums2 pointer to find larger element
            }
            // Case 3: nums2 element is larger
            else {
                i++;  // Move nums1 pointer to find larger element
            }
        }

        // Convert the List<Integer> to int[] array
        int[] result = new int[tempList.size()];
        for (int k = 0; k < tempList.size(); k++) {
            result[k] = tempList.get(k);
        }

        return result;
    }
}

12. Leaders in an Array

Method : Right-to-Left Traversal

Logic

• Traverse the array from right to left.

• Keep track of the maximum value seen so far (maxFromRight).

• If the current element is greater than maxFromRight, it is a leader.

• Store all such elements in a result list.

• Reverse the list at the end to maintain the original order.

// Given an integer array nums, return a list of all the leaders in the array
// A leader in an array is an element whose value is strictly greater than all elements to its right in the given array. The rightmost element is always a leader. The elements in the leader array must appear in the order they appear in the nums array.
// Examples:
// Input: nums = [1, 2, 5, 3, 1, 2]
// Output: [5, 3, 2]
// Explanation: 2 is the rightmost element, 3 is the largest element in the index range [3, 5], 5 is the largest element in the index range [2, 5]

class Solution {
    /**
     * Rearranges an array to alternate positive and negative numbers.
     * Maintains the relative order of positive and negative numbers.
     * 
     * @param nums Input array with equal number of positives and negatives
     * @return Rearranged array with alternating positives and negatives
     * 
     * Time Complexity: O(n) - Single pass through the array
     * Space Complexity: O(n) - For the result array
     */
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];  // Result array

        // Initialize pointers for positive and negative positions
        // Positives start at even indices (0, 2, 4...)
        // Negatives start at odd indices (1, 3, 5...)
        int pos = 0;
        int neg = 1;

        for (int num : nums) {
            if (num >= 0) {
                // Place positive number at current positive position
                res[pos] = num;
                pos += 2;  // Move to next even index
            } else {
                // Place negative number at current negative position
                res[neg] = num;
                neg += 2;  // Move to next odd index
            }
        }

        return res;
    }
}

13. Print the matrix in spiral manner

Method : Using 4 Boundaries

We define four pointers to keep track of the unvisited boundaries:

• top – starting row

• bottom – ending row

• left – starting column

• right – ending column

Repeat the process:

1. Traverse left to right across the top row.

2. Traverse top to bottom down the rightmost column.

3. Traverse right to left across the bottom row (if still valid).

4. Traverse bottom to top up the leftmost column (if still valid).

Shrink boundaries after each direction:

• After step 1, top++

• After step 2, right--

• After step 3, bottom--

• After step 4, left++

// Given an integer array nums of even length consisting of an equal number of positive and negative integers.Return the answer array in such a way that the given conditions are met:
// Every consecutive pair of integers have opposite signs.
// For all integers with the same sign, the order in which they were present in nums is preserved.
// The rearranged array begins with a positive integer.
// Examples:
// Input : nums = [2, 4, 5, -1, -3, -4]
// Output : [2, -1, 4, -3, 5, -4]
// Explanation: The positive number 2, 4, 5 maintain their relative positions and -1, -3, -4 maintain their relative positions

class Solution {
    /**
     * Returns all elements of the matrix in spiral order.
     * 
     * @param matrix 2D input array (m x n)
     * @return List of elements in spiral order
     * 
     * Time Complexity: O(m*n) - Visits each element exactly once
     * Space Complexity: O(1) - Excluding the output list
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        // Handle empty matrix case
        if (matrix == null || matrix.length == 0) {
            return result;
        }

        // Initialize boundaries
        int top = 0;                    // Topmost row
        int bottom = matrix.length - 1; // Bottommost row
        int left = 0;                   // Leftmost column
        int right = matrix[0].length - 1; // Rightmost column

        while (top <= bottom && left <= right) {
            // Traverse from left to right along top boundary
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++; // Move top boundary down

            // Traverse from top to bottom along right boundary
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--; // Move right boundary left

            // Check if there's a row remaining
            if (top <= bottom) {
                // Traverse from right to left along bottom boundary
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--; // Move bottom boundary up
            }

            // Check if there's a column remaining
            if (left <= right) {
                // Traverse from bottom to top along left boundary
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++; // Move left boundary right
            }
        }

        return result;
    }
}

14. Pascal's Triangle I

What is Pascal's Triangle?

Pascal’s Triangle looks like this:

Row 1:       1
Row 2:      1 1
Row 3:     1 2 1
Row 4:    1 3 3 1
Row 5:   1 4 6 4 1

Each number is the sum of the two numbers directly above it.

So for example:

• Row = 4, Column = 2 → Value = 3

Formula Behind Pascal’s Triangle

Each value in Pascal’s Triangle is a binomial coefficient:
C(n, k) = n! / (k! * (n - k)!)

But to avoid using factorials (which can overflow), we use this multiplicative formula:

This is done iteratively for better efficiency and to avoid overflow.

Approach

1. Convert 1-indexed (r, c) to 0-indexed (n, k):

   • n = r - 1

   • k = c - 1

2. Use the multiplicative formula to compute C(n, k) efficiently:

   • Multiply and divide step-by-step.

3. Use symmetry of Pascal’s triangle:

   • C(n, k) = C(n, n - k) → compute the smaller value to reduce iterations.

// Q - Given two integers r and c, return the value at the rth row and cth column (1-indexed) in a Pascal's Triangle.

// In Pascal's triangle:

// The first row has one element with a value of 1.
// Each row has one more element in it than its previous row.
// The value of each element is equal to the sum of the elements directly above it when arranged in a triangle format.

// Examples:
// Input: r = 4, c = 2

// Output: 3

// Explanation: The Pascal's Triangle is as follows:
// 1
// 1 1
// 1 2 1
// 1 3 3 1

// Thus, value at row 4 and column 2 = 3

class Solution {
    public int pascalTriangleI(int r, int c) {
        // Convert from 1-based to 0-based indices
        r = r - 1;
        c = c - 1;

        // Use the property C(n, k) = C(n, n-k) to minimize the number of multiplications/divisions
        if (c > r - c) {
            c = r - c;
        }

        // Base cases: C(n, 0) and C(n, n) are both 1
        if (c == 0 || c == r) {
            return 1;
        }

        int res = 1;
        // Compute the combination value using the multiplicative formula:
        // C(n, k) = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1)
        // This loop calculates the result step-by-step to avoid overflow
        for (int i = 0; i < c; i++) {
            // Multiply by (n - i) to build the numerator part
            res = res * (r - i);
            // Divide by (i + 1) to build the denominator part
            res = res / (i + 1);
        }

        return res;
    }
}

15. Pascal's Triangle II

Intuition

Pascal's Triangle is built using combinations:

• The element at index i in row n (0-based) is: C(n, i) = n! / (i! * (n - i)!)

Instead of calculating factorials (which are slow and can overflow), we use an optimized iterative method:

C(n, i) = C(n, i-1) * (n - i + 1) / i

This means:

• Start with 1 (because C(n, 0) = 1)

• Use the previous value to calculate the next one in O(1) time

Step-by-Step Logic

1. Convert to 0-based row index → n = r - 1

2. Initialize an array of size r to store the row.

3. First value is always 1.

4. For every i from 1 to r-1: ans[i] = ans[i-1] * (r - i) / i

// Q - Given an integer r, return all the values in the rth row (1-indexed) in Pascal's Triangle in correct order.

// In Pascal's triangle:

// The first row has one element with a value of 1.
// Each row has one more element in it than its previous row.
// The value of each element is equal to the sum of the elements directly above it when arranged in a triangle format.

// Examples:
// Input: r = 4
// Output: [1, 3, 3, 1]
// Explanation: The Pascal's Triangle is as follows:
// 1
// 1 1
// 1 2 1
// 1 3 3 1
// Thus the 4th row is [1, 3, 3, 1]

class Solution {
    /**
     * Generates the r-th row (1-indexed) of Pascal's Triangle using combinatorial properties.
     * Each element in the row is calculated iteratively using the formula:
     * C(n, k) = C(n, k-1) * (n - k + 1) / k, where n = r-1 (0-indexed row).
     * 
     * @param r The 1-based row index of Pascal's Triangle
     * @return An array representing the r-th row of Pascal's Triangle
     * 
     * Time Complexity: O(r) - Computes each element in constant time
     * Space Complexity: O(r) - Stores the row elements
     */
    public int[] pascalTriangleII(int r) {
        // Initialize the result array for the r-th row (has r elements)
        int[] ans = new int[r];

        // First element is always 1 (C(n, 0) = 1)
        ans[0] = 1;

        // Iteratively compute each element in the row
        for (int i = 1; i < r; i++) {
            // Formula: ans[i] = previous_element * (row_length - i) / current_index
            // Equivalent to C(n, i) = C(n, i-1) * (n - i + 1) / i 
            // Here, n = r-1 (0-indexed row), so (n - i + 1) = (r - 1 - i + 1) = r - i
            ans[i] = (ans[i - 1] * (r - i)) / i;
        }

        return ans;
    }
}

16 . Pascal's Triangle III

Intuition

Each row in Pascal’s Triangle represents the binomial coefficients C(n, k) where:

• First and last elements are always 1

• Every other element is the sum of the two elements directly above it from the previous row

Instead of summing from the triangle above, we can use combinatorics to compute each row directly:

C(n, k) = C(n, k-1) * (n - k + 1) / k

This helps us build each row efficiently without generating the full triangle above it.

Step-by-Step Logic

1. Create an outer list to hold all rows.

2. Loop from row 1 to n.

3. For each row:

   • Start with 1

   • Use the formula: next = previous * (r - i) / i

   • Add values to the list.

4. Return the full triangle list.

// Q - Given an integer n, return the first n (1-Indexed) rows of Pascal's triangle.
// In Pascal's triangle:
// The first row has one element with a value of 1.
// Each row has one more element in it than its previous row.
// The value of each element is equal to the sum of the elements directly above it when arranged in a triangle format.

// Input: n = 4
// Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
// Explanation: The Pascal's Triangle is as follows:
// 1
// 1 1
// 1 2 1
// 1 3 3 1
// 1st Row has its value set to 1.
// All other cells take their value as the sum of the values directly above them

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

class Solution {
    /**
     * Generates the first n rows of Pascal's Triangle.
     * 
     * @param n The number of rows to generate (1-indexed)
     * @return A list of lists representing Pascal's Triangle up to the n-th row
     * 
     * Time Complexity: O(n²) - Each row is generated in O(r) time, where r is the row number
     * Space Complexity: O(n²) - Stores all n rows with total n(n+1)/2 elements
     */
    public List<List<Integer>> pascalTriangleIII(int n) {
        List<List<Integer>> pascalTriangle = new ArrayList<>();

        // Generate each row from 1 to n (1-indexed)
        for (int r = 1; r <= n; r++) {
            pascalTriangle.add(generateRow(r));
        }

        return pascalTriangle;
    }

    /**
     * Generates the r-th row (1-indexed) of Pascal's Triangle using combinatorial properties.
     * Each element is calculated iteratively using the formula:
     * C(r-1, k) = C(r-1, k-1) * (r - k) / k, where C(n, k) is the binomial coefficient.
     * 
     * @param r The 1-based row index to generate
     * @return A list representing the r-th row of Pascal's Triangle
     * 
     * Time Complexity: O(r) - Computes each element in constant time
     * Space Complexity: O(r) - Stores the row elements
     */
    private List<Integer> generateRow(int r) {
        long ans = 1; // Use long to prevent integer overflow during intermediate calculations
        List<Integer> ansRow = new ArrayList<>();

        // The first element is always 1 (C(r-1, 0) = 1)
        ansRow.add(1);

        // Compute subsequent elements using the multiplicative formula
        for (int i = 1; i < r; i++) {
            ans = ans * (r - i); // Multiply by (r - i) = (n - k + 1) where n = r-1, k = i
            ans = ans / i;        // Divide by current index (k)
            ansRow.add((int) ans); // Cast back to int after calculation
        }

        return ansRow;
    }
}

17. Rotate matrix by 90 degrees

Intuition

To rotate the matrix 90° clockwise, we can follow two simple steps:

Step 1: Transpose the Matrix

Swap rows with columns:

• Convert element at (i, j) to (j, i)

Example:

Original:
1 2 3
4 5 6
7 8 9

After transpose:
1 4 7
2 5 8
3 6 9

Step 2: Reverse Each Row

Swap elements from left to right in each row

After reverse each row:
7 4 1
8 5 2
9 6 3

// Given an N * N 2D integer matrix, rotate the matrix by 90 degrees clockwise.
// The rotation must be done in place, meaning the input 2D matrix must be modified directly.

class Solution {
    /**
     * Rotates a square matrix 90 degrees clockwise in-place using transpose + reverse method.
     * 
     * @param matrix The input square matrix to be rotated (modified in-place)
     * 
     * Time Complexity: O(n²) - Two O(n²) operations (transpose and reverse rows)
     * Space Complexity: O(1) - In-place modification with constant extra space
     */
    public void rotateMatrix(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose the matrix (swap rows and columns across diagonal)
        // This converts rows to columns but not yet in rotated order
        for (int i = 0; i < n; i++) {
            // Start j from i to avoid double swapping elements
            for (int j = i; j < n; j++) {  
                // Swap elements at (i,j) and (j,i)
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Step 2: Reverse each row to complete 90-degree rotation
        // This converts the transposed matrix to final rotated state
        for (int i = 0; i < n; i++) {
            // Only iterate halfway through the row to avoid double swaps
            for (int j = 0; j < n / 2; j++) {
                // Swap elements at (i,j) and (i,n-1-j)
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

18 . Two Sum

Method 1 : Brute Force Approach (Nested Loops)

Steps:

1. Loop over each element in the array with index i.

2. For each i, loop over every element after it with index j.

3. Check if nums[i] + nums[j] == target.

4. If yes, return the indices [i, j].

5. If no pair is found after all checks, return [-1, -1].

Method 2 : HashMap Approach (Single Pass)

Steps:

1. Create an empty HashMap to store number-to-index mappings.

2. Iterate over the array from start to end.

3. For each element nums[i], compute complement = target - nums[i].

4. Check if the complement exists in the HashMap.

   • If yes, return the indices [map.get(complement), i].

   • If no, store the current element and its index in the HashMap.

5. If no pair found by the end, return [-1, -1].

Method 3 : HashMap Approach with Additional Comments & Validation (Same Logic as #2)

Steps:

• Exactly the same as the second approach.

• Emphasis on:

  • Adding elements after checking complement to avoid using the same element twice.

  • Returning indices as soon as a valid pair is found.

  • Clear validation and formatted output in the main method.

Summary Table

import java.util.*;

class Solution {
    /**
     * Finds indices of two distinct elements in the array that sum to the target value.
     * Uses a brute-force approach with nested loops to check all possible pairs.
     * 
     * @param nums    Input array of integers
     * @param target  Target sum value
     * @return        Array containing the two indices (0-based) whose elements sum to target,
     *                or [-1, -1] if no such pair exists
     * 
     * Time Complexity:  O(n²) - Checks all n(n-1)/2 pairs in worst case
     * Space Complexity: O(1)   - Uses constant extra space (only 2-element array)
     */
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[] ans = new int[2];  // Stores the result indices

        // Check all possible pairs (i,j) where j > i
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // If pair found, store indices and return immediately
                if (nums[i] + nums[j] == target) {
                    ans[0] = i;
                    ans[1] = j;
                    return ans;
                }
            }
        }

        // Return sentinel values if no valid pair exists
        return new int[]{-1, -1};
    }

    /**
     * Main method to demonstrate the twoSum functionality with sample input
     */
    public static void main(String[] args) {
        // Sample input: array of 5 elements and target 14
        int[] nums = {2, 6, 5, 8, 11};
        int target = 14;  // 6 (index 1) + 8 (index 3) = 14

        Solution sol = new Solution();
        int[] ans = sol.twoSum(nums, target);

        // Expected output: [1, 3] (indices of 6 and 8)
        System.out.println("This is the answer: [" + ans[0] + ", " + ans[1] + "]");
    }
}

import java.util.*;

class Solution {
    /**
     * Finds indices of two distinct elements in the array that sum to the target value.
     * Uses a HashMap to track number-to-index mappings for O(1) complement lookups.
     * 
     * @param nums    Input array of integers
     * @param target  Target sum value
     * @return        Array containing the two indices (0-based) whose elements sum to target,
     *                or [-1, -1] if no valid pair exists
     * 
     * Time Complexity:  O(n) - Single pass through the array
     * Space Complexity: O(n) - Stores at most n elements in the HashMap
     */
    public int[] twoSum(int[] nums, int target) {
        // Map to store (number -> index) pairs for quick complement lookups
        Map<Integer, Integer> mpp = new HashMap<>();

        // Iterate through each element in the array
        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i];
            int complement = target - currentNum;  // Calculate required complement

            // Check if complement exists in the map
            if (mpp.containsKey(complement)) {
                // Return indices: complement's index and current index
                return new int[]{mpp.get(complement), i};
            }

            // Store current number and its index in the map
            mpp.put(currentNum, i);
        }

        // Return sentinel values if no valid pair found
        return new int[]{-1, -1};
    }
}

public class Main {
    /**
     * Demonstrates the twoSum functionality with sample input
     */
    public static void main(String[] args) {
        // Sample input: Array [2, 6, 5, 8, 11] with target 14
        // Expected output: [1, 3] (6 + 8 = 14)
        int[] nums = {2, 6, 5, 8, 11};
        int target = 14;

        Solution sol = new Solution();
        int[] result = sol.twoSum(nums, target);

        System.out.println("Indices of the two numbers that sum to " + target + ": [" 
                          + result[0] + ", " + result[1] + "]");
    }
}

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

class Solution {
    /**
     * Finds indices of two distinct numbers in the array that add up to the target value.
     * Utilizes a HashMap for efficient O(1) lookups of complement values.
     * 
     * @param nums    The input array of integers to search
     * @param target  The target sum value to achieve
     * @return        An array containing the two indices (0-based) of elements that sum to target,
     *                or [-1, -1] if no valid pair exists
     * 
     * @example 
     * Input: nums = [2,7,11,15], target = 9
     * Output: [0,1] (because nums[0] + nums[1] = 2 + 7 = 9)
     * 
     * Time Complexity: O(n) - Single iteration through the array
     * Space Complexity: O(n) - Worst-case storage of all elements in HashMap
     */
    public int[] twoSum(int[] nums, int target) {
        // Map to store number->index pairs for instant complement checks
        Map<Integer, Integer> numToIndexMap = new HashMap<>();

        for (int currentIndex = 0; currentIndex < nums.length; currentIndex++) {
            int currentNumber = nums[currentIndex];
            int complement = target - currentNumber;

            // Check if required complement exists in map first to avoid self-match
            if (numToIndexMap.containsKey(complement)) {
                // Return indices ensuring smaller index comes first
                return new int[]{numToIndexMap.get(complement), currentIndex};
            }

            // Add current number to map after check to prevent duplicate usage
            numToIndexMap.put(currentNumber, currentIndex);
        }

        // Return sentinel value if no solution found
        return new int[]{-1, -1};
    }
}

public class Main {
    /**
     * Demonstrates twoSum functionality with validation
     */
    public static void main(String[] args) {
        // Test case: There's a valid solution at indices 1 and 3 (6 + 8 = 14)
        int[] numbers = {2, 6, 5, 8, 11};
        int targetSum = 14;

        Solution solution = new Solution();
        int[] result = solution.twoSum(numbers, targetSum);

        // Format and print results with verification
        if (result[0] != -1) {
            System.out.printf("Elements at indices [%d, %d] (%d + %d) sum to %d%n",
                result[0], result[1], 
                numbers[result[0]], numbers[result[1]], 
                targetSum);
        } else {
            System.out.println("No valid pair found");
        }
    }
}

19. 3 Sum

Method 1 : Brute Force Approach (Three Nested Loops)

Steps:

1. Use three nested loops to consider every possible triplet (i, j, k) where i < j < k.

2. For each triplet, check if the sum of nums[i] + nums[j] + nums[k] is zero.

3. If yes, create a list of these three numbers.

4. Sort the triplet to avoid duplicates in different orders.

5. Add the sorted triplet to a HashSet to ensure uniqueness.

6. After all triplets are checked, convert the HashSet to a list and return it.

Method 2 : HashSet-Based Two Sum Approach (Reduce to 2-Sum for Each Element)

Steps:

1. Iterate through the array and fix one element at a time (nums[i]).

2. For the remaining elements after i, use a HashSet to find two numbers that sum to -nums[i].

3. For each element nums[j] after i, calculate the required third number as -(nums[i] + nums[j]).

4. Check if this required number exists in the HashSet of seen elements.

5. If yes, create a sorted triplet and add it to the HashSet to avoid duplicates.

6. Add nums[j] to the HashSet for future lookup.

7. After finishing, convert the HashSet of triplets to a list and return it.

Method 3 : Two-Pointer Approach (Optimized)

Steps:

1. Sort the input array.

2. Iterate over the array, fixing one element at a time (nums[i]).

3. Use two pointers, left starting from i+1 and right starting from the end of the array.

4. Calculate the sum of nums[i] + nums[left] + nums[right].

5. If the sum is less than zero, move left pointer right to increase the sum.

6. If the sum is greater than zero, move right pointer left to decrease the sum.

7. If the sum is zero, record the triplet.

8. Skip duplicate elements to avoid repeated triplets.

9. Move both pointers inward to find new pairs.

10. Return the list of unique triplets.

Summary Table

import java.util.*;

class Solution {
    /**
     * Finds all unique triplets in the array that sum to zero using a brute-force approach.
     * This method checks all possible triplets (i, j, k) where i < j < k and stores unique combinations.
     * 
     * @param nums The input array of integers
     * @return A list of lists containing all unique triplets that sum to zero
     * 
     * Time Complexity: O(n³) - Three nested loops iterate over all possible triplets
     * Space Complexity: O(n³) - In the worst case, all O(n³) triplets are stored in the set
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // Use a HashSet to automatically handle duplicate triplets
        Set<List<Integer>> tripletSet = new HashSet<>();
        int n = nums.length;

        // Generate all possible triplets using three nested loops
        for (int i = 0; i < n - 2; i++) {          // First element
            for (int j = i + 1; j < n - 1; j++) {  // Second element
                for (int k = j + 1; k < n; k++) {  // Third element
                    // Check if current triplet sums to zero
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        // Create and sort the triplet to ensure uniqueness in the set
                        List<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[k]);
                        Collections.sort(temp);  // Sorting enables duplicate detection
                        tripletSet.add(temp);
                    }
                }
            }
        }

        // Convert the set to a list for final output
        return new ArrayList<>(tripletSet);
    }
}

public class Main {
    /**
     * Demonstrates the threeSum functionality with a sample input
     */
    public static void main(String[] args) {
        // Sample input: [-1, 0, 1, 2, -1, -4]
        // Expected output: [[-1, -1, 2], [-1, 0, 1]]
        int[] nums = {-1, 0, 1, 2, -1, -4};

        Solution sol = new Solution();
        List<List<Integer>> result = sol.threeSum(nums);

        // Print the result with basic formatting
        System.out.println("Unique triplets summing to zero:");
        for (List<Integer> triplet : result) {
            System.out.print("[");
            for (int num : triplet) {
                System.out.print(num + " ");
            }
            System.out.print("] ");
        }
    }
}

import java.util.*;

class Solution {
    /**
     * Finds all unique triplets in the array that sum to zero using a hashset-based approach.
     * This method reduces the problem to a two-sum scenario for each element, using a hashset
     * to track potential complements and ensure O(1) lookups.
     * 
     * @param nums The input array of integers
     * @return A list of lists containing all unique triplets that sum to zero
     * 
     * Time Complexity: O(n²) - Two nested loops (n elements × n iterations)
     * Space Complexity: O(n) - Stores up to n elements in hashset and result set
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // Set to store unique triplets (prevents duplicates via sorted entries)
        Set<List<Integer>> tripletSet = new HashSet<>();
        int n = nums.length;

        // Iterate through each potential first element of the triplet
        for (int i = 0; i < n; i++) {
            // Hashset to track elements seen between nums[i+1] and nums[j-1]
            Set<Integer> seenElements = new HashSet<>();

            // Look for second and third elements in subsequent positions
            for (int j = i + 1; j < n; j++) {
                int requiredThird = - (nums[i] + nums[j]);

                // Check if required third element exists in previously seen elements
                if (seenElements.contains(requiredThird)) {
                    // Create and sort triplet to ensure set uniqueness
                    List<Integer> triplet = new ArrayList<>(
                        Arrays.asList(nums[i], nums[j], requiredThird)
                    );
                    Collections.sort(triplet);
                    tripletSet.add(triplet);
                }

                // Add current element to hashset for future complement checks
                seenElements.add(nums[j]);
            }
        }

        return new ArrayList<>(tripletSet);
    }

    public static void main(String[] args) {
        // Sample input: Classic three-sum test case
        int[] nums = {-1, 0, 1, 2, -1, -4};

        Solution sol = new Solution();
        List<List<Integer>> result = sol.threeSum(nums);

        // Formatted output with clear element visualization
        System.out.println("Unique Zero-Sum Triplets:");
        for (List<Integer> triplet : result) {
            System.out.printf("(%d, %d, %d) ",
                triplet.get(0), triplet.get(1), triplet.get(2));
        }
    }
}

import java.util.*;

class Solution {
    /**
     * Finds all unique triplets in the array that sum to zero using a two-pointer approach.
     * 
     * Algorithm Steps:
     * 1. Sort the array to enable efficient duplicate skipping and two-pointer technique.
     * 2. Iterate through each element as the first element of potential triplets.
     * 3. Use two pointers (left/right) to find pairs that complete the zero-sum triplet.
     * 4. Skip duplicate elements to ensure unique triplets in the result.
     * 
     * @param nums Input array of integers
     * @return List of unique triplets that sum to zero
     * 
     * Time Complexity: O(n²) - Sorting O(n log n) + nested loops O(n²)
     * Space Complexity: O(1) - Excluding output storage (in-place sorting)
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);  // Critical for two-pointer approach and duplicate handling

        for (int i = 0; i < nums.length; i++) {
            // Skip duplicate first elements
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;        // Second element pointer
            int right = nums.length - 1;  // Third element pointer

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    left++;  // Need larger sum
                } else if (sum > 0) {
                    right--;  // Need smaller sum
                } else {
                    // Found valid triplet
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Skip duplicates for left and right pointers
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }
}

public class Main {
    /**
     * Demonstrates threeSum functionality with sample input
     */
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};  // Sample input
        Solution sol = new Solution();

        // Expected output: [-1, -1, 2], [-1, 0, 1]
        List<List<Integer>> result = sol.threeSum(nums);

        System.out.println("Unique Zero-Sum Triplets:");
        for (List<Integer> triplet : result) {
            System.out.println(triplet);
        }
    }
}

19. 4 Sum

Method 1 : Brute-force Approach (O(n⁴))

Steps :

• Check all combinations of 4 elements using 4 nested loops.

• Use a Set to store sorted quadruplets (to avoid duplicates).

• Sort each quadruplet before adding to the set to ensure uniqueness.

Method 2 : Better HashSet-based Approach (O(n³))

Steps:

• Fix two elements using loops.

• For the remaining part, use a HashSet to track needed complement values for the fourth element.

• Still uses a Set of lists for de-duplication.

Method 3 : Optimized Two-Pointer Approach (O(n³))

Steps:

• Sort the array first.

• Fix first two elements using loops.

• Use two-pointer approach to find the remaining two numbers.

• Skip duplicates during iteration.

Summary Comparison

import java.util.*;

class Solution {
    /**
     * Finds all unique quadruplets in the array that sum to the target value using a brute-force approach.
     * This method checks all possible combinations of four elements and stores unique quadruplets.
     * 
     * @param nums    Input array of integers
     * @param target  Target sum value
     * @return        List of lists containing all unique quadruplets that sum to the target
     * 
     * Time Complexity: O(n⁴) - Four nested loops iterate over all possible quadruplets
     * Space Complexity: O(n⁴) - Worst-case storage of all possible quadruplets in the set
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // Use a set to automatically handle duplicate quadruplets
        Set<List<Integer>> quadrupletSet = new HashSet<>();
        int n = nums.length;

        // Check all possible combinations of four distinct elements
        for (int first = 0; first < n; first++) {            // First element
            for (int second = first + 1; second < n; second++) {  // Second element
                for (int third = second + 1; third < n; third++) { // Third element
                    for (int fourth = third + 1; fourth < n; fourth++) { // Fourth element

                        // Calculate sum using long to prevent integer overflow
                        long sum = (long)nums[first] + nums[second] + nums[third] + nums[fourth];

                        if (sum == target) {
                            // Create and sort the quadruplet to ensure uniqueness in the set
                            List<Integer> temp = Arrays.asList(
                                nums[first], 
                                nums[second], 
                                nums[third], 
                                nums[fourth]
                            );
                            Collections.sort(temp);
                            quadrupletSet.add(temp);
                        }
                    }
                }
            }
        }

        // Convert set to list for final output
        return new ArrayList<>(quadrupletSet);
    }

    /**
     * Demonstrates fourSum functionality with sample input
     */
    public static void main(String[] args) {
        // Sample input: [4, 3, 3, 4, 4, 2, 1, 2, 1, 1] with target 9
        // Expected output contains combinations like [1,1,3,4], [1,2,2,4], etc.
        int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
        int target = 9;

        Solution sol = new Solution();
        List<List<Integer>> result = sol.fourSum(nums, target);

        System.out.println("Unique Quadruplets Summing to " + target + ":");
        for (List<Integer> quad : result) {
            System.out.printf("[%d, %d, %d, %d]%n", 
                quad.get(0), quad.get(1), quad.get(2), quad.get(3));
        }
    }
}

import java.util.*;

class Solution {

    /**
     * Finds all unique quadruplets in the array that sum up to the given target.
     * 
     * @param nums   Input array of integers
     * @param target The desired target sum
     * @return       A list of all unique quadruplets that sum to target
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // This list will store the final answer containing unique quadruplets
        List<List<Integer>> ans = new ArrayList<>();

        // Get the length of the array
        int n = nums.length;

        // Using a set to store quadruplets and ensure uniqueness (no duplicates)
        Set<List<Integer>> set = new HashSet<>();

        // Iterate over the array for the first element of the quadruplet
        for (int i = 0; i < n; i++) {
            // Second element of the quadruplet
            for (int j = i + 1; j < n; j++) {
                // HashSet to store third element complements for current i, j
                Set<Long> hashset = new HashSet<>();

                // Third element of the quadruplet
                for (int k = j + 1; k < n; k++) {
                    /*
                     * Calculate the sum of the first three elements
                     * Use long to avoid integer overflow for large values
                     */
                    long sum = (long) nums[i] + nums[j] + nums[k];

                    // Calculate the fourth value required to reach the target
                    long fourth = target - sum;

                    /*
                     * If the required fourth value is already present in the hashset,
                     * it means we have previously seen an element that, along with
                     * nums[i], nums[j], and nums[k], will form a valid quadruplet
                     */
                    if (hashset.contains(fourth)) {
                        // Create the quadruplet
                        List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k], (int) fourth);

                        // Sort the list to handle unordered duplicates
                        Collections.sort(temp);

                        // Add the sorted quadruplet to the set (ensures uniqueness)
                        set.add(temp);
                    }

                    /*
                     * Add the current element to the hashset to help find
                     * matching complements in future iterations
                     */
                    hashset.add((long) nums[k]);
                }
            }
        }

        /*
         * Convert the set of unique quadruplets to a list and return
         */
        ans.addAll(set);
        return ans;
    }

    // Main method for testing the fourSum function
    public static void main(String[] args) {
        // Sample input array
        int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
        // Target sum
        int target = 9;

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the fourSum function
        List<List<Integer>> ans = sol.fourSum(nums, target);

        // Print the result
        System.out.println("The quadruplets are:");
        for (List<Integer> quad : ans) {
            System.out.print("[");
            for (int num : quad) {
                System.out.print(num + " ");
            }
            System.out.println("]");
        }
    }
}

import java.util.*;

class Solution {
    /**
     * Finds all unique quadruplets in the array that sum to the target using a two-pointer approach.
     * 
     * Algorithm Steps:
     * 1. Sort the array to enable efficient duplicate skipping and two-pointer technique.
     * 2. Iterate through each pair of elements (i, j) as the first two elements of potential quadruplets.
     * 3. Use two pointers (k, l) to find pairs that complete the target sum.
     * 4. Skip duplicate elements to ensure unique quadruplets in the result.
     * 
     * @param nums    Input array of integers
     * @param target  Target sum value
     * @return        List of unique quadruplets that sum to the target
     * 
     * Time Complexity: O(n³) - Sorting O(n log n) + three nested loops O(n³)
     * Space Complexity: O(1) - Excluding output storage (in-place sorting)
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);  // Critical for two-pointer approach and duplicate handling

        // Iterate through each potential first element (i) of the quadruplet
        for (int i = 0; i < n; i++) {
            // Skip duplicate first elements
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // Iterate through each potential second element (j) > i
            for (int j = i + 1; j < n; j++) {
                // Skip duplicate second elements
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int k = j + 1;  // Third element pointer (left)
                int l = n - 1;  // Fourth element pointer (right)

                // Two-pointer technique to find remaining two elements
                while (k < l) {
                    // Use long to prevent integer overflow during sum calculation
                    long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];

                    if (sum < target) {
                        k++;  // Need larger sum → move left pointer right
                    } else if (sum > target) {
                        l--;  // Need smaller sum → move right pointer left
                    } else {
                        // Found valid quadruplet
                        ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));

                        // Skip duplicates for left and right pointers
                        while (k < l && nums[k] == nums[k + 1]) k++;
                        while (k < l && nums[l] == nums[l - 1]) l--;
                        k++;
                        l--;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * Demonstrates fourSum functionality with sample input
     */
    public static void main(String[] args) {
        // Sample input: [4, 3, 3, 4, 4, 2, 1, 2, 1, 1] with target 9
        // Expected output includes [1,1,3,4], [1,2,2,4], etc.
        int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
        int target = 9;

        Solution sol = new Solution();
        List<List<Integer>> result = sol.fourSum(nums, target);

        System.out.println("Unique Quadruplets Summing to " + target + ":");
        for (List<Integer> quad : result) {
            System.out.printf("[%d, %d, %d, %d]%n", 
                quad.get(0), quad.get(1), quad.get(2), quad.get(3));
        }
    }
}

20. Sort an array of 0's 1's and 2's

Method 1: Brute-force Counting Sort (O(n))

Steps:

1. Count the number of 0s, 1s, and 2s using three counters.

2. Overwrite the array: fill with all 0s, then 1s, then 2s based on the counts.

Method 2: Dutch National Flag Algorithm (O(n))

Steps:

1. Use three pointers:

   • low for 0s zone

   • mid for traversal

   • high for 2s zone

2. While mid <= high:

   • If nums[mid] == 0: Swap with low, increment both.

   • If nums[mid] == 1: Just increment mid.

   • If nums[mid] == 2: Swap with high, decrement high (don’t move mid yet).

Summary Comparison

class Solution {
    /**
     * Sorts an array containing 0s, 1s, and 2s in-place using the Dutch National Flag algorithm.
     * 
     * Algorithm Steps:
     * 1. Use three pointers: low (tracking 0s), mid (tracking 1s), high (tracking 2s)
     * 2. Traverse the array with mid pointer:
     *    a. 0 → swap with low pointer, increment both
     *    b. 1 → just increment mid
     *    c. 2 → swap with high pointer, decrement high
     * 
     * @param nums The input array to be sorted (modified in-place)
     * 
     * Time Complexity: O(n) - Single pass through the array
     * Space Complexity: O(1) - In-place sorting with constant extra space
     */
    public void sortZeroOneTwo(int[] nums) {
        int low = 0;          // Tracks the boundary of 0s
        int mid = 0;          // Current element being processed
        int high = nums.length - 1;  // Tracks the boundary of 2s

        while (mid <= high) {
            switch (nums[mid]) {
                case 0:
                    // Swap 0 to the low boundary
                    swap(nums, low, mid);
                    low++;  // Expand 0s boundary
                    mid++;  // Process next element
                    break;

                case 1:
                    // 1s stay in the middle, just move mid pointer
                    mid++;
                    break;

                case 2:
                    // Swap 2 to the high boundary
                    swap(nums, mid, high);
                    high--;  // Expand 2s boundary
                    // Don't increment mid - new element needs checking
                    break;
            }
        }
    }

    /**
     * Helper method to swap two elements in an array
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 0, 1, 1, 0, 2};

        Solution sol = new Solution();
        sol.sortZeroOneTwo(nums);

        System.out.print("Sorted array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        // Output: 0 0 1 1 2 2
    }
}

class Solution {
    /**
     * Sorts an array containing only 0s, 1s, and 2s using a counting technique.
     * This implementation counts occurrences of each value and reconstructs the array.
     * 
     * @param nums The array to be sorted (modified in-place)
     * 
     * Time Complexity: O(n) - Two linear passes through the array
     * Space Complexity: O(1) - Uses constant extra space for counters
     */
    public void sortZeroOneTwo(int[] nums) {
        // Initialize counters for 0s, 1s, and 2s
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;

        // First pass: Count frequency of each value
        for (int num : nums) {
            if (num == 0) cnt0++;
            else if (num == 1) cnt1++;
            else cnt2++;
        }

        // Second pass: Rebuild array in sorted order
        int index = 0;

        // Fill 0s (first cnt0 positions)
        while (cnt0-- > 0) nums[index++] = 0;

        // Fill 1s (next cnt1 positions)
        while (cnt1-- > 0) nums[index++] = 1;

        // Fill 2s (remaining positions)
        while (cnt2-- > 0) nums[index++] = 2;
    }

    /**
     * Demonstrates the sorting functionality with a sample array
     */
    public static void main(String[] args) {
        int[] nums = {0, 2, 1, 2, 0, 1};  // Input: [0,2,1,2,0,1]

        Solution sol = new Solution();
        sol.sortZeroOneTwo(nums);

        System.out.println("After sorting:");
        for (int num : nums) {
            System.out.print(num + " ");  // Output: 0 0 1 1 2 2 
        }
    }
}

21 . Kadane's Algorithm

Method 1: Kadane's Algorithm (Optimized O(n))

Steps:

1. Initialize two variables:

   • maxSum = nums[0]: stores the best sum found so far.

   • currentSum = nums[0]: stores the sum of the current subarray.

2. Iterate through the array from index 1 to n-1.

   • At each index, decide:

     • Start new subarray from current element: nums[i]

     • Or extend the current one: currentSum + nums[i]

   • Update maxSum whenever currentSum exceeds it.

3. Return maxSum.

Method 2: Kadane with Subarray Indices

Steps:

1. Track maxSum, currentSum, currentStart, and final subarray range (maxStart, maxEnd).

2. Reset currentSum and currentStart if sum goes below 0.

3. When currentSum > maxSum, update maxSum and range.

Method 3: Optimized O(n²) (Prefix-like)

Steps:

1. Fix each startIdx and loop over all endIdx >= startIdx.

2. Add elements from startIdx to endIdx to form subarrays.

3. Track and update maxSum.

Summary

---

class Solution {
    /**
     * Finds the maximum sum of any contiguous subarray using Kadane's algorithm.
     * 
     * Algorithm Steps:
     * 1. Track current subarray sum and maximum sum found
     * 2. For each element, decide whether to extend current subarray or start new
     * 3. Update maximum sum when current subarray sum exceeds previous maximum
     * 
     * @param nums Input array of integers
     * @return Maximum sum of any contiguous subarray
     * 
     * Time Complexity: O(n) - Single pass through the array
     * Space Complexity: O(1) - Uses only constant extra space
     */
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Decide whether to start new subarray or extend current one
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // Update maximum sum if current subarray is larger
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        Solution sol = new Solution();
        int maxSum = sol.maxSubArray(arr);

        System.out.println("The maximum subarray sum is: " + maxSum); // Output: 6
    }
}

class Solution {
    /**
     * Finds the maximum sum of any contiguous subarray using an optimized O(n²) approach.
     * This method efficiently calculates subarray sums by building upon previous computations.
     * 
     * @param nums Input array of integers
     * @return Maximum sum of any contiguous subarray
     * 
     * Time Complexity: O(n²) - Two nested loops iterating over all subarray starting points
     * Space Complexity: O(1) - Uses only constant extra space
     */
    public int maxSubArray(int[] nums) {
        // Initialize maximum sum with the smallest possible integer value
        int maxSum = Integer.MIN_VALUE;

        // Iterate over all possible starting indices for subarrays
        for (int startIdx = 0; startIdx < nums.length; startIdx++) {
            int currentSubarraySum = 0;

            // Calculate sum for all subarrays starting at startIdx and ending at endIdx
            for (int endIdx = startIdx; endIdx < nums.length; endIdx++) {
                // Add current element to running subarray sum
                currentSubarraySum += nums[endIdx];

                // Update maximum sum if current subarray sum is greater
                maxSum = Math.max(maxSum, currentSubarraySum);
            }
        }

        return maxSum;
    }

    /**
     * Demonstrates functionality with sample input
     */
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};  // Max subarray: [4, -1, 2, 1] sum=6

        Solution sol = new Solution();
        int result = sol.maxSubArray(arr);

        System.out.println("The maximum subarray sum is: " + result);
    }
}

class Solution {
    /**
     * Finds the maximum sum of any contiguous subarray using Kadane's algorithm.
     * 
     * Algorithm Steps:
     * 1. Track current subarray sum and maximum sum found
     * 2. For each element, add to current sum
     * 3. If current sum exceeds maximum, update maximum
     * 4. Reset current sum to 0 if it becomes negative
     * 
     * @param nums Input array of integers
     * @return Maximum sum of any contiguous subarray
     * 
     * Time Complexity: O(n) - Single pass through the array
     * Space Complexity: O(1) - Uses only constant extra space
     */
    public int maxSubArray(int[] nums) {
        long maxSum = Long.MIN_VALUE;  // Handles minimum integer overflow cases
        long currentSum = 0;

        for (int num : nums) {
            currentSum += num;

            // Update maximum sum if current subarray sum is larger
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }

            // Reset current sum if it becomes negative
            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return (int) maxSum;  // Cast back to int after calculations
    }

    /**
     * Demonstrates functionality with sample input
     */
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};  // Max subarray: [4, -1, 2, 1] sum=6

        Solution sol = new Solution();
        int result = sol.maxSubArray(arr);

        System.out.println("The maximum subarray sum is: " + result);  // Output: 6
    }
}

class Solution {
    /**
     * Finds the maximum sum of any contiguous subarray and prints the subarray using Kadane's algorithm.
     * 
     * Algorithm Steps:
     * 1. Track current subarray sum and maximum sum found
     * 2. Track start/end indices of both current and maximum subarrays
     * 3. Update indices when new maximum is found
     * 4. Reset current sum when it becomes negative
     * 
     * @param nums Input array of integers
     * @return Maximum sum of any contiguous subarray
     * 
     * Time Complexity: O(n) - Single pass through the array
     * Space Complexity: O(1) - Uses only constant extra space
     */
    public int maxSubArray(int[] nums) {
        long maxSum = Long.MIN_VALUE;  // Maximum subarray sum found
        long currentSum = 0;           // Sum of current subarray
        int currentStart = 0;          // Start index of current subarray
        int maxStart = -1, maxEnd = -1; // Indices of maximum subarray

        for (int i = 0; i < nums.length; i++) {
            // Track new subarray start when resetting sum
            if (currentSum == 0) {
                currentStart = i;
            }

            currentSum += nums[i];

            // Update maximum sum and indices when new maximum found
            if (currentSum > maxSum) {
                maxSum = currentSum;
                maxStart = currentStart;
                maxEnd = i;
            }

            // Reset current sum if it becomes negative
            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        // Print the maximum subarray
        printSubarray(nums, maxStart, maxEnd);

        return (int) maxSum;
    }

    /**
     * Helper method to print the subarray between given indices
     */
    private void printSubarray(int[] nums, int start, int end) {
        System.out.print("Maximum sum subarray: [");
        for (int i = start; i <= end; i++) {
            System.out.print(nums[i] + (i < end ? ", " : ""));
        }
        System.out.println("]");
    }

    /**
     * Demonstrates functionality with sample input
     */
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};  // Max subarray: [4, -1, 2, 1]

        Solution sol = new Solution();
        int result = sol.maxSubArray(arr);

        System.out.println("Maximum subarray sum: " + result);  // Output: 6
    }
}

22 . Majority Element-I

Method 1. Moore’s Voting Algorithm (Optimal – O(n) Time, O(1) Space)

Idea:
Find a potential candidate that could be the majority element by canceling out different elements. Then verify if it's really the majority.

Steps:

• First Pass:

  • Start with count = 0 and an arbitrary candidate.

  • For every number:

    • If count is 0 → Set current number as new candidate.

    • If number equals candidate → Increment count.

    • Else → Decrement count.

• Second Pass:

  • Count actual occurrences of the candidate.

  • If it appears more than n / 2 times → Return it.

  • Else → Return -1.

Why it works:
If there’s a number that appears more than half the time, it will survive the cancellation process and emerge as a candidate.

When to use:
When you want optimal space and time, and a majority element is guaranteed or must be verified.

Method 2. HashMap-Based Frequency Count (Brute-force – O(n) Time, O(n) Space)

Idea:
Count the frequency of every number using a HashMap and check if any count exceeds n / 2.

Steps:

• Loop through the array and store frequencies in a HashMap.

• Traverse the map entries:

  • If any key has a value > n / 2 → Return that key.

• If none found → Return -1.

Why it works:
It explicitly checks frequency using extra space, so it's simple and reliable.

When to use:

• When you want quick implementation without worrying about space.

• When input size is small or space isn’t a constraint.

Method 3: Moore’s Voting (Alternate Version with Comments and Improved Naming)

Idea:
Same as Method 1, just with clearer variable names (cnt and el), useful for learning.

Steps:

• Find a candidate element using Moore’s Voting (same logic).

• Count how many times that element occurs.

• If count > n / 2 → Return it, else -1.

Why this version?
It emphasizes clarity and explanation, useful for understanding step-by-step what happens during the process.

When to use:
Same as Method 1, but this version is great when you’re trying to understand the logic deeply.

---

class Solution {
    /**
     * Finds the majority element in an array using Moore's Voting Algorithm.
     * A majority element appears more than n/2 times where n is the array length.
     * 
     * @param nums The input array of integers
     * @return The majority element, or -1 if none exists
     * 
     * Time Complexity: O(n) - Two linear passes through the array
     * Space Complexity: O(1) - Uses only constant extra space
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = -1;

        // First pass: Find potential majority candidate
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else {
                count += (num == candidate) ? 1 : -1;
            }
        }

        // Second pass: Verify candidate is majority
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        return (count > nums.length / 2) ? candidate : -1;
    }

    /**
     * Demonstrates functionality with sample input
     */
    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};  // Majority element: 2

        Solution sol = new Solution();
        int result = sol.majorityElement(arr);

        System.out.println("The majority element is: " + result);  // Output: 2
    }
}

import java.util.*;

class Solution {
    // Function to find the majority element (element appearing more than n/2 times)
    public int majorityElement(int[] nums) {
        // Store the length of the input array
        int n = nums.length;

        // Create a HashMap to track the frequency of each element
        // Key: array element, Value: occurrence count
        HashMap<Integer, Integer> map = new HashMap<>();

        // Iterate through each element in the array
        for (int num : nums) {
            // Update frequency count for current element:
            // - If the element is new, initialize its count to 1
            // - If the element exists, increment its current count by 1
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // Check each entry in the map to find the majority element
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // If an element's count exceeds n/2, it is the majority element
            if (entry.getValue() > n / 2) {
                return entry.getKey(); // Return the majority element
            }
        }

        // Return -1 if no majority element exists (should not occur per problem constraints)
        return -1;
    }

    // Main method to test the majorityElement function
    public static void main(String[] args) {
        // Test array: majority element is 2 (appears 4 times in 7 elements)
        int[] arr = {2, 2, 1, 1, 1, 2, 2};

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Call the function and store the result
        int ans = sol.majorityElement(arr);

        // Display the result
        System.out.println("The majority element is: " + ans);
    }
}

import java.util.*;

class Solution {
    // Function to find the majority element using Moore's Voting Algorithm
    public int majorityElement(int[] nums) {
        // Store the length of the input array
        int n = nums.length;

        // Initialize counter and candidate element
        int cnt = 0;        // Tracks net frequency advantage of candidate
        int el = 0;         // Stores current majority candidate

        // First pass: Find potential majority candidate
        for (int i = 0; i < n; i++) {
            // When counter is zero, we pick a new candidate
            if (cnt == 0) {
                cnt = 1;    // Reset counter for new candidate
                el = nums[i]; // Set current element as candidate
            } 
            // If current element matches candidate, strengthen its position
            else if (el == nums[i]) {
                cnt++;      // Increment counter for same element
            } 
            // Current element differs from candidate, weaken its position
            else {
                cnt--;      // Decrement counter for different element
            }
        }

        /* Second pass: Verify if candidate is actual majority element */
        int cnt1 = 0;       // Counter for candidate frequency
        for (int i = 0; i < n; i++) {
            // Count occurrences of candidate element
            if (nums[i] == el) {
                cnt1++;
            }
        }

        // Confirm candidate has strict majority (> n/2 occurrences)
        if (cnt1 > (n / 2)) {
            return el;      // Return validated majority element
        }

        // Return -1 if no majority exists (per problem constraints, this may be omitted)
        return -1;
    }

    // Main method to test the solution
    public static void main(String[] args) {
        // Test array: majority element is 2 (appears 4 times in 7 elements)
        int[] arr = {2, 2, 1, 1, 1, 2, 2};

        // Create Solution instance
        Solution sol = new Solution();

        // Find and store majority element
        int ans = sol.majorityElement(arr);

        // Print result
        System.out.println("The majority element is: " + ans);
    }
}

24. Majority Element-II

Method 1: Moore’s Voting Algorithm

We cancel out elements that are different from each other. If a majority exists, the final candidate will survive.

Steps:

1. First Pass:

   • Keep a candidate and a count.

   • If count == 0, pick current number as candidate.

   • If the current number is the same as candidate, increment count, else decrement it.

2. Second Pass:

   • Count occurrences of candidate.

   • If count > n / 2, return it.

   • Else, return -1.

Method 2: HashMap Frequency Counter

Use a HashMap to store the count of each element. Then check if any element appears more than n / 2 times.

Steps:

1. Initialize a HashMap:

   • Create a HashMap<Integer, Integer> to store the frequency (count) of each element.

2. Count Frequencies:

   • Loop through the array.

   • For each element:

     • If it's not in the map, add it with count 1.

     • If it's already in the map, increment its count by 1.

3. Check for Majority:

   • Loop through the entries in the map.

   • If any element has a count greater than n / 2 (where n is the size of the array), return that element as the majority.

4. No Majority Found:

   • If no such element is found after checking all entries, return -1.

Summary

import java.util.*;

class Solution {
    // Function to find all elements appearing more than n/3 times
    public List<Integer> majorityElementTwo(int[] nums) {
        // Store length of input array
        int n = nums.length;

        // Initialize result list for majority elements
        List<Integer> result = new ArrayList<>();

        // Traverse each element to check for majority status
        for (int i = 0; i < n; i++) {
            /* Skip if current element is already in results 
               or matches the first found majority element */
            if (result.size() == 0 || result.get(0) != nums[i]) {
                int cnt = 0;  // Reset counter for current element

                // Count frequency of current element in entire array
                for (int j = 0; j < n; j++) {
                    if (nums[j] == nums[i]) {
                        cnt++;
                    }
                }

                // Verify if element meets n/3 threshold
                if (cnt > (n / 3)) {
                    result.add(nums[i]);  // Add to results
                }
            }

            /* Optimization: Maximum two majority elements possible 
               (since 3*(n/3+1) > n), so break early */
            if (result.size() == 2) {
                break;
            }
        }

        return result;  // Return found majority elements
    }

    public static void main(String[] args) {
        int[] arr = {11, 33, 33, 11, 33, 11};  // Test array

        Solution sol = new Solution();  // Create solution instance
        List<Integer> ans = sol.majorityElementTwo(arr);  // Find majority elements

        // Print results
        System.out.print("The majority elements are: ");
        for (int it : ans) {
            System.out.print(it + " ");
        }
        System.out.println();
    }
}

import java.util.*;

class Solution {
    // Function to find all elements appearing more than n/3 times
    public List<Integer> majorityElementTwo(int[] nums) {
        // Store length of input array
        int n = nums.length;

        // Initialize result list for majority elements
        List<Integer> result = new ArrayList<>();

        // Create frequency map to track element counts
        Map<Integer, Integer> freqMap = new HashMap<>();

        // Calculate minimum frequency threshold for majority (n/3 + 1)
        int minThreshold = n / 3 + 1;

        // Iterate through each element in the array
        for (int i = 0; i < n; i++) {
            int num = nums[i];

            // Update frequency count for current element
            int count = freqMap.getOrDefault(num, 0) + 1;
            freqMap.put(num, count);

            /* Check if current element just reached majority threshold
               and hasn't been added to results yet */
            if (count == minThreshold) {
                result.add(num);  // Add to majority elements list
            }

            /* Optimization: Since there can be at most 2 majority elements
               (3*(n/3+1) > n), break early once we find two */
            if (result.size() == 2) {
                break;
            }
        }

        return result;  // Return found majority elements
    }

    public static void main(String[] args) {
        // Test array with two majority elements (11 and 33 both appear 3 times in 6 elements)
        int[] arr = {11, 33, 33, 11, 33, 11};

        Solution sol = new Solution();  // Create solution instance
        List<Integer> ans = sol.majorityElementTwo(arr);  // Find majority elements

        // Format and print results
        System.out.print("The majority elements are: ");
        for (int element : ans) {
            System.out.print(element + " ");
        }
        System.out.println();
    }
}

import java.util.*;

class Solution {
    // Function to find all elements appearing more than n/3 times using Boyer-Moore Voting Algorithm
    public List<Integer> majorityElementTwo(int[] nums) {
        // Store length of input array
        int n = nums.length;

        /* Initialize candidate elements and their vote counts
           Using MIN_VALUE as placeholder for uninitialized candidates */
        int candidate1 = Integer.MIN_VALUE;
        int candidate2 = Integer.MIN_VALUE;
        int votes1 = 0, votes2 = 0;

        /* First Pass: Find potential majority candidates */
        for (int num : nums) {
            /* Case 1: Current element matches candidate1
               Increase its vote count */
            if (num == candidate1) {
                votes1++;
            } 
            /* Case 2: Current element matches candidate2
               Increase its vote count */
            else if (num == candidate2) {
                votes2++;
            } 
            /* Case 3: Reset candidate1 slot if votes are zero
               (with additional check to avoid duplicate candidates) */
            else if (votes1 == 0) {
                candidate1 = num;
                votes1 = 1;
            } 
            /* Case 4: Reset candidate2 slot if votes are zero
               (with additional check to avoid duplicate candidates) */
            else if (votes2 == 0) {
                candidate2 = num;
                votes2 = 1;
            } 
            /* Case 5: Current element differs from both candidates
               Decrement both vote counts (opposition vote) */
            else {
                votes1--;
                votes2--;
            }
        }

        /* Second Pass: Verify candidates meet n/3 threshold */
        int count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == candidate1) count1++;
            if (num == candidate2) count2++;
        }

        // Calculate minimum required occurrences (n/3 + 1)
        int minRequired = n / 3 + 1;
        List<Integer> result = new ArrayList<>();

        // Add candidate1 if it meets threshold
        if (count1 >= minRequired) result.add(candidate1);
        /* Add candidate2 if it meets threshold and is distinct from candidate1
           (prevents duplicate entries when only one candidate exists) */
        if (count2 >= minRequired && candidate1 != candidate2) result.add(candidate2);

        return result;  // Return validated majority elements
    }

    public static void main(String[] args) {
        // Test array: both 11 and 33 appear 3 times (n=6, min=3)
        int[] arr = {11, 33, 33, 11, 33, 11};

        Solution sol = new Solution();  // Create solution instance
        List<Integer> ans = sol.majorityElementTwo(arr);  // Find majority elements

        // Format and print results
        System.out.print("The majority elements are: ");
        for (int element : ans) {
            System.out.print(element + " ");
        }
        System.out.println();
    }
}

25. Find the repeating and missing number

Method 1: Brute Force with Counting Each Number

Check frequency of each number from 1 to n.

Steps:

1. Initialize repeating = -1, missing = -1.

2. Loop from i = 1 to n:

   • Count how many times i appears in the array.

   • If count is 2 → repeating = i.

   • If count is 0 → missing = i.

3. Break early if both are found.

4. Return [repeating, missing].

Method 2: Frequency Array (Hashing)

Use a frequency array to count how often each number appears.

Steps:

1. Initialize freq[] of size n+1 with all zeros.

2. Loop through input nums[], increment freq[nums[i]] for each number.

3. Loop i = 1 to n:

   • If freq[i] == 0 → missing = i.

   • If freq[i] == 2 → repeating = i.

4. Return [repeating, missing].

Method 3: Mathematical Formula (Sum and Square Sum)

Use math to find difference between expected and actual values.

Steps:

1. Let n = nums.length.

2. Calculate:

   • sumNatural = n(n+1)/2

   • sumSquaresNatural = n(n+1)(2n+1)/6

3. Loop through nums[]:

   • Compute actualSum = sum of all elements

   • Compute actualSumSquares = sum of squares of all elements

4. Calculate:

   • diff1 = actualSum - sumNatural = X - Y

   • diff2 = actualSumSquares - sumSquaresNatural = X² - Y²

5. From identity:

   • X² - Y² = (X - Y)(X + Y)

   • So, X + Y = diff2 / diff1

6. Solve for:

   • repeating = (diff1 + sumXY) / 2

   • missing = (sumXY - diff1) / 2

7. Return [repeating, missing].

Summary

---

import java.util.*;

class Solution {
    // Function to find the repeating and missing numbers in an array of size `n` containing numbers 1 to `n`
    public int[] findMissingRepeatingNumbers(int[] nums) {
        // Store the size of the array
        int n = nums.length; 
        // Initialize variables to store results
        int repeating = -1, missing = -1;

        /* Iterate through each number from 1 to n to check:
           - Which number appears twice (repeating)
           - Which number is missing (0 occurrences) */
        for (int i = 1; i <= n; i++) {
            // Reset counter for current number i
            int cnt = 0;

            // Count occurrences of current number i in the array
            for (int j = 0; j < n; j++) {
                if (nums[j] == i) cnt++;
            }

            /* Update results based on occurrence count:
               - If count=2 → i is repeating
               - If count=0 → i is missing */
            if (cnt == 2) repeating = i;
            else if (cnt == 0) missing = i;

            /* Optimization: Early termination if both 
               repeating and missing numbers are found */
            if (repeating != -1 && missing != -1)
                break;
        }

        // Return result as [repeating, missing]
        return new int[] {repeating, missing};
    }

    public static void main(String[] args) {
        // Test array: contains numbers 1-8 with 5 repeated and 8 missing
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};

        // Create solution instance
        Solution sol = new Solution();

        // Get result
        int[] result = sol.findMissingRepeatingNumbers(nums);

        // Format and print output
        System.out.println("The repeating and missing numbers are: {" + 
                           result[0] + ", " + result[1] + "}");
    }
}

import java.util.*;

class Solution {
    // Function to find the repeating and missing numbers in an array of size `n` containing numbers 1 to `n`
    public int[] findMissingRepeatingNumbers(int[] nums) {
        // Store the size of the array
        int n = nums.length;

        /* Create a frequency array (hash) of size n+1 to count occurrences:
           - Index 0 unused (numbers are 1..n)
           - Initialize all counts to 0 */
        int[] freq = new int[n + 1];

        /* First Pass: Count occurrences of each number in the array
           - nums[i] will be between 1..n
           - Increment frequency count for each occurrence */
        for (int i = 0; i < n; i++) {
            freq[nums[i]]++;  // Increment count for current number
        }

        // Initialize result variables
        int repeating = -1, missing = -1;

        /* Second Pass: Identify repeating and missing numbers
           - Iterate through expected numbers 1 to n
           - Check frequency counts in the frequency array */
        for (int i = 1; i <= n; i++) {
            if (freq[i] == 2) {
                repeating = i;  // Number appears twice (repeating)
            } else if (freq[i] == 0) {
                missing = i;    // Number never appears (missing)
            }

            /* Optimization: Early termination if both
               repeating and missing numbers are found */
            if (repeating != -1 && missing != -1) {
                break;
            }
        }

        // Return result as [repeating, missing]
        return new int[]{repeating, missing};
    }

    public static void main(String[] args) {
        // Test array: contains numbers 1-8 with 5 repeated and 8 missing
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};

        // Create solution instance
        Solution sol = new Solution();

        // Get result
        int[] result = sol.findMissingRepeatingNumbers(nums);

        // Format and print output
        System.out.println("The repeating and missing numbers are: {" + 
                           result[0] + ", " + result[1] + "}");
    }
}

import java.util.*;

class Solution {
    // Function to find the repeating and missing numbers in an array of size `n` containing numbers 1 to `n`
    public int[] findMissingRepeatingNumbers(int[] nums) {
        // Store size of array as long to prevent integer overflow
        long n = nums.length;

        // Calculate sum of first n natural numbers: Sₙ = n(n+1)/2
        long sumNatural = (n * (n + 1)) / 2;

        // Calculate sum of squares of first n natural numbers: S₂ₙ = n(n+1)(2n+1)/6
        long sumSquaresNatural = (n * (n + 1) * (2 * n + 1)) / 6;

        // Initialize variables to store actual sum and sum of squares
        long actualSum = 0;
        long actualSumSquares = 0;

        // Calculate actual sum and sum of squares from array elements
        for (int num : nums) {
            actualSum += num;                          // Accumulate element values
            actualSumSquares += (long) num * num;      // Accumulate squared element values
        }

        /* Calculate differences:
           diff1 = actualSum - sumNatural → (X - Y) where:
             X = repeating number, 
             Y = missing number */
        long diff1 = actualSum - sumNatural;

        /* Calculate diff2 = actualSumSquares - sumSquaresNatural → (X² - Y²)
           Then: (X² - Y²) = (X-Y)(X+Y) */
        long diff2 = actualSumSquares - sumSquaresNatural;

        /* Derive (X + Y) from the identity: 
           (X+Y) = (X²-Y²)/(X-Y) = diff2/diff1 */
        long sumXY = diff2 / diff1;

        /* Solve for X and Y using:
           X = [(X-Y) + (X+Y)] / 2
           Y = [(X+Y) - (X-Y)] / 2 */
        long repeating = (diff1 + sumXY) / 2;   // Repeating number (X)
        long missing = (sumXY - diff1) / 2;     // Missing number (Y)

        // Return results as integer array [repeating, missing]
        return new int[]{(int) repeating, (int) missing};
    }

    public static void main(String[] args) {
        // Test array: contains numbers 1-8 with 5 repeated and 8 missing
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};

        // Create solution instance
        Solution sol = new Solution();

        // Get result
        int[] result = sol.findMissingRepeatingNumbers(nums);

        // Format and print output
        System.out.printf("The repeating and missing numbers are: {%d, %d}%n", 
                          result[0], result[1]);
    }
}

26. Count Inversions

An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j].
You are asked to count total number of such inversions in the array.

Method 1: Merge Sort + Arrays.copyOfRange

Idea:
Use the Merge Sort technique. While merging two sorted halves, if right[j] < left[i], it means all remaining elements in left[] (from i to end) form inversions with right[j].

Steps:

1. numberOfInversions(nums):

• Starts merge sort and returns total inversion count from mergeSortAndCount(nums, 0, n - 1).

2. mergeSortAndCount(nums, left, right):

• Divide the array into two halves.

• Count inversions in:

  • Left half

  • Right half

  • During merging (cross inversions)

• Return the sum of all.

3. mergeAndCount(nums, left, mid, right):

• Create subarrays using Arrays.copyOfRange for both halves.

• Merge them:

  • If left[i] <= right[j], no inversion.

  • Else, count all remaining elements in left as inversions.

• Copy merged array back to nums.

• Return inversion count.

Method 2: Merge Sort + In-Place Merge (System.arraycopy) (Optimized)

Idea:
Same logic as above but instead of creating new arrays, it uses a temporary array to merge and directly updates the original array — saves space.

Steps:

1. numberOfInversions(nums):

• Handles edge cases.

• Calls mergeSort(nums, 0, nums.length - 1).

2. mergeSort(arr, low, high):

• Divide array recursively into left and right.

• Count inversions from both halves.

• Count during merge and return the total.

3. merge(arr, low, mid, high):

• Create a temporary array temp[] to merge both sorted halves.

• If arr[left] <= arr[right], copy normally.

• Else, inversion found → count = (mid - left + 1)

• Copy temp[] back to original array using System.arraycopy.

• Return inversion count.

---

import java.util.*;

class Solution {
    // Function to find the number of inversions in an array using Merge Sort
    public long numberOfInversions(int[] nums) {
        // Call helper function to perform merge sort and count inversions
        return mergeSortAndCount(nums, 0, nums.length - 1);
    }

    // Helper function for merge sort that counts inversions
    private long mergeSortAndCount(int[] nums, int left, int right) {
        long inversionCount = 0;
        if (left < right) {
            // Calculate mid point
            int mid = left + (right - left) / 2;

            // Recursive calls for left and right halves
            inversionCount += mergeSortAndCount(nums, left, mid);
            inversionCount += mergeSortAndCount(nums, mid + 1, right);

            // Merge the sorted halves and count cross inversions
            inversionCount += mergeAndCount(nums, left, mid, right);
        }
        return inversionCount;
    }

    // Function to merge two sorted halves and count inversions
    private long mergeAndCount(int[] nums, int left, int mid, int right) {
        // Create temporary arrays for left and right halves
        int[] leftArr = Arrays.copyOfRange(nums, left, mid + 1);
        int[] rightArr = Arrays.copyOfRange(nums, mid + 1, right + 1);

        int i = 0, j = 0, k = left;
        long inversionCount = 0;

        // Merge while counting inversions
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                nums[k++] = leftArr[i++];
            } else {
                // Right element is smaller → inversion found
                nums[k++] = rightArr[j++];
                /* All remaining elements in leftArr form inversions
                   with current right element (mid - left - i + 1) */
                inversionCount += (mid - left + 1) - i;
            }
        }

        // Copy remaining elements
        while (i < leftArr.length) nums[k++] = leftArr[i++];
        while (j < rightArr.length) nums[k++] = rightArr[j++];

        return inversionCount;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {5, 4, 3, 2, 1};

        // Create solution instance
        Solution sol = new Solution();

        // Get inversion count
        long result = sol.numberOfInversions(nums);

        // Print result
        System.out.println("The number of inversions is: " + result);
    }
}

class Solution {

    /* Merge function to count inversions and merge sorted halves */
    private long merge(int[] arr, int low, int mid, int high) {
        // Create temporary array for merging sorted halves
        int[] temp = new int[high - low + 1];
        int left = low;      // Starting index of left subarray
        int right = mid + 1; // Starting index of right subarray
        int index = 0;       // Index for temp array
        long inversionCount = 0; // Count of inversions found in this merge

        // Traverse both halves until one is exhausted
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                // Left element is smaller → no inversion
                temp[index++] = arr[left++];
            } else {
                // Right element is smaller → inversion(s) found
                temp[index++] = arr[right++];
                /* All elements from current left to end of left subarray (mid) 
                   form inversions with current right element */
                inversionCount += (mid - left + 1);
            }
        }

        // Copy any remaining elements in left subarray
        while (left <= mid) {
            temp[index++] = arr[left++];
        }

        // Copy any remaining elements in right subarray
        while (right <= high) {
            temp[index++] = arr[right++];
        }

        // Copy merged elements from temp back to original array
        System.arraycopy(temp, 0, arr, low, temp.length);

        return inversionCount;
    }

    /* Recursive merge sort function with inversion counting */
    private long mergeSort(int[] arr, int low, int high) {
        long inversionCount = 0;
        // Only proceed if there are at least 2 elements
        if (low < high) {
            int mid = low + (high - low) / 2; // Prevent overflow

            // Recursively sort left half and count inversions
            inversionCount += mergeSort(arr, low, mid);

            // Recursively sort right half and count inversions
            inversionCount += mergeSort(arr, mid + 1, high);

            // Merge sorted halves and count cross-halve inversions
            inversionCount += merge(arr, low, mid, high);
        }
        return inversionCount;
    }

    /* Public interface to count inversions in the entire array */
    public long numberOfInversions(int[] nums) {
        // Edge case: empty or single-element array has no inversions
        if (nums == null || nums.length <= 1) return 0;

        // Start recursive merge sort from index 0 to last index
        return mergeSort(nums, 0, nums.length - 1);
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {5, 4, 3, 2, 1}; // Test array (reverse sorted = max inversions)
        Solution sol = new Solution();
        long result = sol.numberOfInversions(nums);
        System.out.println("The number of inversions is: " + result);
    }
}

27. Reverse Pairs

Method 1: Brute Force

Check every possible pair (i, j) and count how many satisfy the reverse pair condition.

Steps:

1. Initialize a counter cnt = 0.

2. Loop through each element with index i from 0 to n-1.

3. For each i, loop through j = i + 1 to n - 1:

   • If nums[i] > 2 * nums[j], it's a reverse pair → increment cnt.

4. Return the final count cnt.

Method 2: Optimized using Merge Sort (Divide and Conquer)

Use modified merge sort to count reverse pairs during the merge step, just like how we count inversions.

Steps:

1. Call the reversePairs() method, which triggers a recursive merge sort helper mergeSort(arr, low, high).

2. In mergeSort:

   • Base case: If the subarray has only 1 element (low >= high), return 0.

   • Find mid: mid = (low + high) / 2.

   • Recursively:

     • Count reverse pairs in left half: mergeSort(arr, low, mid)

     • Count reverse pairs in right half: mergeSort(arr, mid + 1, high)

   • Count cross reverse pairs using countPairs(arr, low, mid, high).

   • Merge both halves into a sorted segment with merge(arr, low, mid, high).

3. In countPairs:

   • For each element in the left half (i = low to mid):

     • Move a pointer j in the right half (mid+1 to high) as long as:

         arr[i] > 2 * arr[j]
       

     • Count how many such js exist for each i and add it to the total count.

4. In merge:

   • Merge the two sorted halves into a temporary array temp[].

   • Copy back the merged result into the original array.

5. Finally, return the total count of reverse pairs from the recursive calls.

Summary

---

import java.util.*;

class Solution {
    /* 
     * Function to count reverse pairs in an array.
     * A reverse pair is defined as a pair (i, j) where:
     *   i < j and nums[i] > 2 * nums[j]
     * 
     * @param nums: Input array of integers
     * @return: Count of reverse pairs
     */
    public int reversePairs(int[] nums) {
        // Delegate the counting to helper function
        return countPairs(nums, nums.length); 
    }

    /* 
     * Helper function to count pairs satisfying the reverse pair condition
     * 
     * @param nums: Input array of integers
     * @param n: Length of the array
     * @return: Count of valid reverse pairs
     */
    private int countPairs(int[] nums, int n) {
        // Initialize counter for reverse pairs
        int cnt = 0;

        /* 
         * Outer loop: Traverse each element as potential 'i' in pair (i, j)
         * - i ranges from 0 to n-1
         */
        for (int i = 0; i < n; i++) {
            /* 
             * Inner loop: Check elements after i as potential 'j' in pair (i, j)
             * - j ranges from i+1 to n-1 (ensuring i < j)
             */
            for (int j = i + 1; j < n; j++) {
                /* 
                 * Check reverse pair condition: nums[i] > 2 * nums[j]
                 * - Using direct multiplication for comparison
                 */
                if (nums[i] > 2 * nums[j]) {
                    // Condition satisfied: increment reverse pair count
                    cnt++; 
                }
            }
        }
        // Return total count of reverse pairs found
        return cnt; 
    }

    // Main method for testing
    public static void main(String[] args) {
        // Test array: [6, 4, 1, 2, 7]
        int[] nums = {6, 4, 1, 2, 7}; 

        // Create solution instance
        Solution sol = new Solution(); 

        // Compute reverse pairs count
        int cnt = sol.reversePairs(nums); 

        // Output result
        System.out.println("The number of reverse pairs is: " + cnt);
    }
}

import java.util.*;

class Solution {

    /**
     * Main function to start reverse pair count.
     * A reverse pair is defined as (i, j) such that:
     *     i < j and nums[i] > 2 * nums[j]
     *
     * @param nums - Input array of integers
     * @return Count of reverse pairs
     */
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    /**
     * Modified Merge Sort function that:
     * 1. Sorts the array
     * 2. Counts reverse pairs across halves
     *
     * @param nums - The array to process
     * @param low  - Starting index
     * @param high - Ending index
     * @return Number of reverse pairs in this range
     */
    private int mergeSort(int[] nums, int low, int high) {
        if (low >= high) return 0;

        int mid = low + (high - low) / 2;
        int count = 0;

        // Count reverse pairs in left and right halves
        count += mergeSort(nums, low, mid);
        count += mergeSort(nums, mid + 1, high);

        // Count reverse pairs between left and right halves
        int j = mid + 1;
        for (int i = low; i <= mid; i++) {
            // Find how many elements on right side satisfy nums[i] > 2 * nums[j]
            while (j <= high && (long)nums[i] > 2L * nums[j]) {
                j++;
            }
            count += (j - (mid + 1));
        }

        // Merge the two sorted halves
        merge(nums, low, mid, high);

        return count;
    }

    /**
     * Standard merge function to combine two sorted halves
     *
     * @param nums - The original array
     * @param low  - Start of the first half
     * @param mid  - End of the first half
     * @param high - End of the second half
     */
    private void merge(int[] nums, int low, int mid, int high) {
        List<Integer> temp = new ArrayList<>();
        int left = low;
        int right = mid + 1;

        // Merge elements from both halves into temp list
        while (left <= mid && right <= high) {
            if (nums[left] <= nums[right]) {
                temp.add(nums[left++]);
            } else {
                temp.add(nums[right++]);
            }
        }

        // Add remaining elements from the left half
        while (left <= mid) {
            temp.add(nums[left++]);
        }

        // Add remaining elements from the right half
        while (right <= high) {
            temp.add(nums[right++]);
        }

        // Copy sorted elements back to original array
        for (int i = low; i <= high; i++) {
            nums[i] = temp.get(i - low);
        }
    }

    // Sample test case
    public static void main(String[] args) {
        int[] nums = {6, 4, 1, 2, 7};
        Solution sol = new Solution();
        int result = sol.reversePairs(nums);
        System.out.println("The number of reverse pairs is: " + result);
    }
}

27. Maximum Product Subarray in an Array

Method 1: Brute Force (Nested Loops)

Idea:
Try all possible subarrays and calculate their product. Track the maximum product found.

Steps:

1. Initialize result with the first element.

2. Loop through each index i as the starting point.

3. For each i, initialize currentProduct = nums[i].

4. Update result = max(result, currentProduct) (in case the subarray is of size 1).

5. Expand subarray to include elements from j = i+1 to end:

   • Multiply: currentProduct *= nums[j]

   • Update result = max(result, currentProduct)

6. Return result as the final answer.

Method 2: Optimized (Dynamic Programming)

Idea:
Maintain running values of both maxSoFar and minSoFar at every step since a negative number can become positive when multiplied by another negative.

Steps:

1. Initialize:

   • maxSoFar = nums[0] (max product ending at index i)

   • minSoFar = nums[0] (min product ending at index i)

   • maxProduct = nums[0] (global maximum product)

2. Loop from i = 1 to n-1:

   • Store current maxSoFar in a temp variable (to use in minSoFar update)

   • Update:

       maxSoFar = max(nums[i], nums[i] * maxSoFar, nums[i] * minSoFar);
       minSoFar = min(nums[i], nums[i] * temp,     nums[i] * minSoFar);
     

   • Update maxProduct = max(maxProduct, maxSoFar)

3. Return maxProduct

---

class Solution {
    /**
     * Function to find the maximum product of any contiguous subarray.
     * Uses dynamic programming to track maximum and minimum products at each position.
     * 
     * @param nums: Input array of integers
     * @return: Maximum product of any contiguous subarray
     */
    public int maxProduct(int[] nums) {
        // Initialize with the first element
        int maxSoFar = nums[0];  // Maximum product ending at current position
        int minSoFar = nums[0];  // Minimum product ending at current position
        int maxProduct = nums[0]; // Global maximum product found so far

        // Iterate through the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            // Store current maxSoFar before update for minSoFar calculation
            int temp = maxSoFar;

            /* Update maxSoFar: maximum of:
             *   - Current element alone (starting new subarray)
             *   - Current element times previous max (positive multiplier)
             *   - Current element times previous min (negative * negative case) */
            maxSoFar = Math.max(nums[i], Math.max(nums[i] * maxSoFar, nums[i] * minSoFar));

            /* Update minSoFar: minimum of:
             *   - Current element alone (starting new subarray)
             *   - Current element times previous max (positive * negative case)
             *   - Current element times previous min (negative multiplier) */
            minSoFar = Math.min(nums[i], Math.min(nums[i] * temp, nums[i] * minSoFar));

            // Update global maximum product if current maxSoFar is greater
            maxProduct = Math.max(maxProduct, maxSoFar);
        }

        return maxProduct;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 3, 7, 1, 2}; // Test array

        Solution sol = new Solution(); // Create solution instance
        int maxProd = sol.maxProduct(nums); // Compute maximum product

        System.out.println("The maximum product subarray: " + maxProd);
    }
}

import java.util.*;

class Solution {
    /**
     * Function to find the maximum product of any contiguous subarray.
     * 
     * Approach:
     * - Iterate through each possible starting index of a subarray
     * - For each starting index, expand the subarray to include subsequent elements
     * - Maintain a running product of the current subarray
     * - Continuously update the maximum product found
     * 
     * Time Complexity: O(n²) - For each starting index, we process up to n elements
     * Space Complexity: O(1) - Uses only constant extra space
     * 
     * @param nums Input array of integers
     * @return Maximum product of any contiguous subarray
     */
    public int maxProduct(int[] nums) {
        // Initialize result with the first element of the array
        int result = nums[0];

        /* Iterate through each element as a potential starting point for subarrays */
        for (int i = 0; i < nums.length; i++) {
            // Initialize product with current element (subarray of size 1)
            int currentProduct = nums[i];

            /* Update result for the single-element subarray case
               (could be the maximum product) */
            result = Math.max(result, currentProduct);

            /* Expand subarray to include subsequent elements */
            for (int j = i + 1; j < nums.length; j++) {
                // Multiply current product by next element in subarray
                currentProduct *= nums[j];

                /* Update result with maximum value between:
                   - current maximum result
                   - product of current subarray (from i to j) */
                result = Math.max(result, currentProduct);
            }
        }

        // Return the maximum product found among all subarrays
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 3, 7, 1, 2}; // Test array

        // Create solution instance
        Solution sol = new Solution();

        // Compute maximum product subarray
        int maxProd = sol.maxProduct(nums);

        // Print result
        System.out.println("The maximum product subarray: " + maxProd);
    }
}

29. Merge two sorted arrays without extra space

We are given two sorted arrays:

• nums1[] of size m + n, where first m elements are valid and rest are 0s (buffer for merging).

• nums2[] of size n.

Our goal is to merge nums2 into nums1 in sorted order, modifying nums1 in-place.

Method 1: Using Extra Space (Simple Merge Like Merge Sort)

Steps:

1. Create a new array merged[] of size m + n.

2. Use two pointers:

   • left for nums1

   • right for nums2

3. Compare elements from both arrays:

   • If nums1[left] <= nums2[right], put nums1[left] in merged.

   • Else, put nums2[right] in merged.

4. After one array is done, copy the remaining elements from the other.

5. Finally, copy all elements of merged[] into nums1[].

Method 2: Two Pointers + Sorting After Swapping (Optimized In-place)

Steps:

1. Start two pointers:

   • left at the end of nums1 (last valid element).

   • right at the beginning of nums2.

2. While both are in range:

   • If nums1[left] > nums2[right], swap the values.

   • Move left-- and right++.

   • Stop if no more swaps are needed (i.e., nums1[left] <= nums2[right]).

3. Now sort:

   • nums1[0...m-1] (since some values were swapped).

   • Entire nums2.

4. Finally, **copy all elements of nums2[] into nums1[m to m+n-1]`.

Method 3: Gap Method (Shell Sort Inspired, Optimal for In-Place Merge)

Steps:

1. Let total length be len = m + n.

2. Start with an initial gap = ceil(len / 2).

3. Loop while gap > 0:

   • Start with two pointers: left = 0, right = left + gap.

   • Compare elements at these pointers:

     • If out of order (left > right), swap.

     • There are 3 cases to handle:

       • Both in nums1

       • One in nums1, one in nums2

       • Both in nums2

   • Move left++, right++ while right < len.

   • Reduce the gap using gap = ceil(gap / 2).

4. After fully comparing/swapping:

   • Copy all of nums2 into nums1[m...m+n-1].

import java.util.*;

class Solution {

    // Function to merge two sorted arrays nums1 and nums2
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        // Create a new array to store the merged result
        int[] merged = new int[m + n];

        // Two pointers to traverse nums1 and nums2
        int left = 0;    // Pointer for nums1
        int right = 0;   // Pointer for nums2
        int index = 0;   // Pointer for merged array

        // Traverse both arrays and insert the smaller element into merged[]
        while (left < m && right < n) {
            if (nums1[left] <= nums2[right]) {
                merged[index++] = nums1[left++];
            } else {
                merged[index++] = nums2[right++];
            }
        }

        // If there are remaining elements in nums1, add them to merged[]
        while (left < m) {
            merged[index++] = nums1[left++];
        }

        // If there are remaining elements in nums2, add them to merged[]
        while (right < n) {
            merged[index++] = nums2[right++];
        }

        // Copy the merged[] elements back to nums1[]
        for (int i = 0; i < m + n; i++) {
            nums1[i] = merged[i];
        }
    }

    public static void main(String[] args) {
        // Initial arrays
        int[] nums1 = {-5, -2, 4, 5, 0, 0, 0}; // nums1 has extra space at the end
        int[] nums2 = {-3, 1, 8};             // nums2 is the second sorted array
        int m = 4, n = 3;                     // m = number of initial elements in nums1, n = size of nums2

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Merge nums2 into nums1
        sol.merge(nums1, m, nums2, n);

        // Output the merged array
        System.out.println("The merged array is:");
        System.out.print("nums1[] = ");
        for (int i = 0; i < m + n; i++) { // Print all merged elements
            System.out.print(nums1[i] + " ");
        }
    }
}

import java.util.*;

class Solution {

    // Function to merge two sorted arrays: nums1 and nums2
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        // 'left' points to the last valid element in nums1
        int left = m - 1;

        // 'right' points to the first element in nums2
        int right = 0;

        /**
         * Goal: Ensure that the largest elements are towards the end
         * We compare elements from the end of nums1 and the start of nums2
         * If an element in nums1 is larger than the one in nums2, we swap them
         * This brings smaller elements to the front (for nums1) and larger ones to the back (in nums2)
         * After swapping, we move left backward and right forward
         */
        while (left >= 0 && right < n) {
            if (nums1[left] > nums2[right]) {
                // Swap the two elements to maintain order
                int temp = nums1[left];
                nums1[left] = nums2[right];
                nums2[right] = temp;

                left--;
                right++;
            } else {
                // If nums1[left] is already smaller or equal, we stop
                break;
            }
        }

        /**
         * After the above loop, we may have disturbed the sorted order.
         * So now we sort both halves:
         * nums1[0...m-1] might be unsorted due to swaps.
         */
        Arrays.sort(nums1, 0, m);

        // Similarly, nums2 might be unsorted now, so we sort it completely
        Arrays.sort(nums2);

        /**
         * Now, we place all elements of nums2 into nums1 starting from index m
         * This is safe because nums1 has enough extra space at the end (size m+n)
         */
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }

    public static void main(String[] args) {
        // Initial arrays
        int[] nums1 = {-5, -2, 4, 5, 0, 0, 0}; // nums1 has extra space for merging
        int[] nums2 = {-3, 1, 8};             // Second sorted array

        int m = 4, n = 3; // m = initial number of elements in nums1, n = size of nums2

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Merge nums2 into nums1
        sol.merge(nums1, m, nums2, n);

        // Print the final merged result
        System.out.println("The merged arrays are:");
        System.out.print("nums1[] = ");
        for (int num : nums1) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

import java.util.*;

class Solution {

    // Function to merge two sorted arrays nums1 and nums2 using the Gap method (Shell sort-like approach)
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        // Total length of the merged array
        int len = m + n;

        // Initial gap: half of the length (rounded up)
        int gap = (len / 2) + (len % 2); // Same as Math.ceil(len / 2.0)

        // Continue the loop until gap becomes 0
        while (gap > 0) {
            int left = 0;              // Pointer to the left element
            int right = left + gap;   // Pointer to the right element (gap apart)

            // Compare elements at left and right while right is within bounds
            while (right < len) {

                // Case 1: left is in nums1 and right is in nums2
                if (left < m && right >= m) {
                    swapIfGreater(nums1, nums2, left, right - m);
                }

                // Case 2: both pointers are in nums2
                else if (left >= m) {
                    swapIfGreater(nums2, nums2, left - m, right - m);
                }

                // Case 3: both pointers are in nums1
                else {
                    swapIfGreater(nums1, nums1, left, right);
                }

                // Move both pointers forward by 1
                left++;
                right++;
            }

            // If the current gap is 1, break the loop
            if (gap == 1) break;

            // Otherwise, reduce the gap for the next iteration
            gap = (gap / 2) + (gap % 2); // Equivalent to Math.ceil(gap / 2.0)
        }

        // Copy the sorted nums2 elements to the end of nums1
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }

    /**
     * Utility function to compare and swap elements from two arrays
     * Swaps arr1[idx1] and arr2[idx2] if arr1[idx1] > arr2[idx2]
     */
    private void swapIfGreater(int[] arr1, int[] arr2, int idx1, int idx2) {
        if (arr1[idx1] > arr2[idx2]) {
            int temp = arr1[idx1];
            arr1[idx1] = arr2[idx2];
            arr2[idx2] = temp;
        }
    }

    public static void main(String[] args) {
        // Example input arrays
        int[] nums1 = {-5, -2, 4, 5, 0, 0, 0}; // nums1 has extra space to hold all elements
        int[] nums2 = {-3, 1, 8};
        int m = 4, n = 3; // m: number of initialized elements in nums1, n: size of nums2

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Call the merge function
        sol.merge(nums1, m, nums2, n);

        // Print the final merged array
        System.out.println("The merged array is:");
        System.out.print("nums1[] = ");
        for (int num : nums1) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

This article is a beginner-friendly guide to working with arrays in Java. It covers how to create and use different types of arrays—like single-dimensional, multidimensional, and ragged arrays—with simple examples. You'll also learn how to handle tasks like searching and sorting, along with tips to improve performance. Along with array we will also learn ArrayLists and when to use them. With these questions you will be able to handle how to think and how to optimise.

Do share your opinion, it matters a lot!!