Arrays

Arrays are fundamental data structures used to store a fixed-size sequence of elements of the same type.

Characteristics:

• Arrays are reference types, but their elements can be of any data type
• They allocate a contiguous block of memory in the system
• Elements are stored sequentially in memory
• Array size cannot be modified after initialization
• Elements can be accessed directly via indexing
• Array indices start at 0

Declaration:

• One-dimensional: int[] arr;
• Two-dimensional: int[][] arr;

Initialization:

• Static: int[] arr = new int[]{1,2,3,4,5};
• Dynamic: int[] arr = new int[5];

Traversal:

• For one-dimensional arrays: for(int i = 0; i < arr.length; i++) or for(int element : arr)
• For two-dimensional arrays: nested for loops

java.util.Arrays Class:

Provides utility methods for array operations:

• Arrays.fill() - fills an array with specified values
• Arrays.sort() - sorts an array (ascending by default)

Lists (Linked Lists)

List Implementation:

1. Import java.util package
2. Create a List object using ArrayList class
3. List list = new ArrayList<>();

Common Methods:

• add(Object element) - appends element to the end
• size() - returns number of elements
• get(int index) - retrieves element at specified position
• isEmpty() - checks if list is empty
• contains(Object o) - checks if list contains specified element
• remove(int index) - removes element at specified position

List Characteristics:

• Maintains insertion order and allows duplicates
• Each element has an index (starting from 0)
• Flexible size compared to arrays

Sorting Algorithms

Array Sorting:

Using Arrays.sort():

Integer[] data = {1,2,3,4,5,1,5,6,2};
// Ascending order
Arrays.sort(data);
System.out.println(Arrays.toString(data));
// Descending order
Arrays.sort(data, (a,b) -> b-a);
System.out.println(Arrays.toString(data));

Collection Sorting:

Using Collections.sort():

ArrayList data = new ArrayList<>();
data.add(1);
data.add(4);
data.add(3);
data.add(5);
data.add(4);
// Ascending order
Collections.sort(data);
System.out.println(data);
// Descending order
Collections.sort(data, (a,b) -> b-a);
System.out.println(data);

Set Collections

Set Definition:

A Set is a collection that doesn't allow duplicate elements and is unordered. HashSet is the primary implementation.

Characteristics:

• Used for deduplication
• Elements are unordered

HashSet Class:

Set set = new HashSet<>();
Set set = new HashSet<>();

Common Methods:

• add(E e) - adds element if not present
• size() - returns number of elements
• remove(Object o) - removes specified element
• contains(Object o) - checks if element exists
• clear() - removes all elements

Map Collections

Map Implementation:

1. Import java.util.Map
2. Create object using HashMap
3. Map map = new HashMap<>();

Characteristics:

• Stores key-value pairs
• Fast access based on keys
• Unordered collection
• Allows one null key

Common Methods:

• put(K key, V value) - adds/updates key-value pair
• get(Object key) - retrieves value by key
• size() - returns number of entries
• entrySet() - returns set of key-value pairs
• getOrDefault(Object key, V defaultValue) - returns value or default

Stack and Queue

Stack Implementation:

1. Import java.util.Stack
2. Stack stack = new Stack<>();

Characteristics:

• Last-In-First-Out (LIFO) principle

Common Methods:

• push(E item) - adds element to top
• pop() - removes and returns top element
• peek() - returns top element without removal
• isEmpty() - checks if stack is empty
• search(Object o) - finds position of element

Queue Implementation:

1. Import java.util.Queue
2. Queue queue = new LinkedList<>();

Characteristics:

• First-In-First-Out (FIFO) principle

Common Methods:

• add(E e) - adds element to queue
• poll() - removes and returns head element
• peek() - returns head element without removal
• isEmpty() - checks if queue is empty
• offer(E e) - adds element if possible
• remove() - removes and returns head
• element() - returns head element
• clear() - removes all elements

Basic Sorting Algorithms

Bubble Sort (O(n²))

Concept: Repeatedly steps through the list, compares adjacent elements and swaps them if they're in the wrong order.

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

Selection Sort (O(n²))

Concept: Finds the minimum element and places it at the beginning, then repeats for the remaining elements.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIdx])
                minIdx = j;
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

Insertion Sort (O(n²))

Concept: Builds the final sorted array one item at a time by inserting each element into its proper position.

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}

Quick Sort (O(n log n))

Concept: Divides the array into two partitions around a pivot element and recursively sorts the partitions.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low-1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;
}

Merge Sort (O(n log n))

Concept: Divides the array into halves, recursively sorts each half, and then merges the sorted halves.

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = l + (r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

private static void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Time Complexity Analysis

Time complexity measures how the runtime of an algorithm grows with the input size. It's typically expressed using Big O notation.

Complexity Classes:

• O(1) - Constant time
• O(log n) - Logarithmic time
• O(n) - Linear time
• O(n log n) - Linearithmic time
• O(n²) - Quadratic time
• O(n³) - Cubic time
• O(2^n) - Exponential time

Guidelines for Problem Constraints:

• n < 100: O(n³) algorithms are acceptable
• n ≤ 1000: O(n²) or O(n² log n) algorithms work
• n < 100,000: O(n) or O(n log n) algorithms are suitable
• n ≤ 1,000,000,000: O(√n) algorithms are needed

Algorithmic Techniques

Enumeration (Brute Force)

Systematically checks all possible solutions to find the correct one.

Simulation

Directly implements the problem's requirements step by step.

Recursion

A function that calls itself to solve smaller instances of the same problem.

public static int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * factorial(n - 1);
}

Prefix Sums

Technique to quickly compute sums of subarrays in O(1) time after O(n) preprocessing.

public static int[] computePrefixSums(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n+1];
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i-1] + arr[i-1];
    }
    return prefix;
}

Difference Arrays

Efficient technique for range updates in O(1) time per operation.

public static void rangeUpdate(int[] diff, int l, int r, int value) {
    diff[l] += value;
    if (r+1 < diff.length) diff[r+1] -= value;
}

Greedy Algorithms

Makes locally optimal choices at each step with the hope of finding a global optimum.

Two Pointers

Uses two pointers traversing a data structure to solve problems efficiently.

• Collision pointers: Move toward each other
• Fast/slow pointers: Move at different speeds

Binary Search

Finds an element in a sorted array by repeatedly dividing the search interval in half.

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Dynamic Programming

Solves complex problems by breaking them down into simpler subproblems and storing their solutions.

Dynamic Programming Approaches

Linear DP

DP problems where states transition in a linear fashion.

public static int longestIncreasingSubsequence(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n];
    int maxLen = 1;
    
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

2D DP

DP problems requiring a two-dimensional state array.

public static int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m+1][n+1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

Knapsack Problems

0/1 Knapsack

Each item can be either included or excluded.

public static int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n+1][capacity+1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = Math.max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][capacity];
}

Unbounded Knapsack

Items can be used multiple times.

public static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity+1];
    
    for (int w = 1; w <= capacity; w++) {
        for (int i = 0; i < n; i++) {
            if (weights[i] <= w) {
                dp[w] = Math.max(dp[w], values[i] + dp[w-weights[i]]);
            }
        }
    }
    return dp[capacity];
}

Bounded Knapsack

Items can be used a limited number of times.

public static int boundedKnapsack(int[] weights, int[] values, int[] counts, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity+1];
    
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= 0; w--) {
            for (int k = 1; k <= counts[i] && k * weights[i] <= w; k++) {
                dp[w] = Math.max(dp[w], values[i] * k + dp[w - weights[i] * k]);
            }
        }
    }
    return dp[capacity];
}

Tree DP

Dynamic programming techniques applied to tree structures.

public static int maxIndependentSet(TreeNode root) {
    if (root == null) return 0;
    
    // Case 1: Exclude current node
    int exclude = maxIndependentSet(root.left) + maxIndependentSet(root.right);
    
    // Case 2: Include current node
    int include = root.value;
    if (root.left != null) {
        include += maxIndependentSet(root.left.left) + maxIndependentSet(root.left.right);
    }
    if (root.right != null) {
        include += maxIndependentSet(root.right.left) + maxIndependentSet(root.right.right);
    }
    
    return Math.max(include, exclude);
}

Search Algorithms

Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking.

public static void dfs(Node node, boolean[] visited) {
    if (node == null) return;
    
    visited[node.index] = true;
    System.out.println(node.value);
    
    for (Node neighbor : node.neighbors) {
        if (!visited[neighbor.index]) {
            dfs(neighbor, visited);
        }
    }
}

Backtracking

Systematic method to try all possible solutions by building and abandoning partial solutions.

public static void backtrack(List current, int[] nums, boolean[] used) {
    if (current.size() == nums.length) {
        // Process solution
        System.out.println(current);
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (!used[i]) {
            used[i] = true;
            current.add(nums[i]);
            
            backtrack(current, nums, used);
            
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

DFS with Pruning

Enhances DFS by eliminating unnecessary branches early.

public static void dfsWithPruning(Node node, int currentSum, int target, boolean[] visited) {
    if (currentSum > target) return; // Prune this branch
    
    if (node == null) return;
    
    visited[node.index] = true;
    currentSum += node.value;
    
    if (currentSum == target) {
        // Process solution
        return;
    }
    
    for (Node neighbor : node.neighbors) {
        if (!visited[neighbor.index]) {
            dfsWithPruning(neighbor, currentSum, target, visited);
        }
    }
    
    visited[node.index] = false;
}