Big O & Complexity Analysis

O(1) Constant Time

int getFirst(int[] arr) {
    return arr[0];  // Single operation
}

O(log n) Logarithmic Time

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Find middle
        
        if (arr[mid] == target) return mid;   // Found it!
        if (arr[mid] < target) left = mid + 1; // Search right half
        else right = mid - 1;                  // Search left half
    }
    return -1;  // Not found
}

O(n) Linear Time

int sum(int[] arr) {
    int total = 0;
    
    for (int num : arr) {
        total += num;  // Visit each element once
    }
    
    return total;
}

O(n log n) Linearithmic Time

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);      // Sort left half
        mergeSort(arr, mid + 1, right); // Sort right half
        merge(arr, left, mid, right);   // Merge sorted halves
    }
}

O(n²) Quadratic Time

void bubbleSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n; i++) {           // Outer: n times
        for (int j = 0; j < n - 1; j++) {   // Inner: n times each
            if (arr[j] > arr[j + 1]) {
                // Swap adjacent elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

O(2ⁿ) Exponential Time

int fib(int n) {
    if (n <= 1) return n;  // Base case
    
    return fib(n - 1) + fib(n - 2);  // Two recursive calls!
}

Advanced Time Complexity Patterns

Let's explore more complex scenarios where the complexity isn't immediately obvious.

Pattern 1: Amortized O(1) - ArrayList Add

// ArrayList.add() - usually O(1), sometimes O(n)
ArrayList list = new ArrayList<>();  // Initial capacity = 10

for (int i = 0; i < 100; i++) {
    list.add(i);  // Amortized O(1)
}

// What's happening internally:
// Adds 1-10: O(1) each - array has space
// Add 11: O(n) - must resize! Copy 10 elements to new array (size 20)
// Adds 12-20: O(1) each
// Add 21: O(n) - resize again! Copy 20 elements to new array (size 40)
// And so on...

Pattern 2: Multiple Loops - Add vs Multiply

// Scenario A: Sequential loops (ADD)
void processData(int[] arr1, int[] arr2) {
    for (int x : arr1) { }  // O(n)
    for (int y : arr2) { }  // O(m)
}
// Total: O(n + m) - different inputs, add them

// Scenario B: Nested loops (MULTIPLY)
void processDataNested(int[] arr1, int[] arr2) {
    for (int x : arr1) {      // O(n)
        for (int y : arr2) {  // O(m) for EACH x
        }
    }
}
// Total: O(n × m) - for each of n, do m work

Pattern 3: Recursion with Multiple Branches

// How many leaves in a complete binary tree of height h?
int countLeaves(TreeNode root, int height) {
    if (height == 0) return 1;  // Leaf node
    
    int left = countLeaves(root.left, height - 1);
    int right = countLeaves(root.right, height - 1);
    
    return left + right;
}

// Time complexity analysis:
// Level 0: 1 call
// Level 1: 2 calls  (each parent calls 2 children)
// Level 2: 4 calls  (2² calls)
// Level 3: 8 calls  (2³ calls)
// ...
// Level h: 2^h calls

// Total calls = 1 + 2 + 4 + 8 + ... + 2^h
//             = 2^(h+1) - 1
//             = O(2^h) where h is height

// If tree has n nodes: h = log(n), so O(2^log n) = O(n)

Pattern 4: Logarithmic Recursion Depth

// Binary search recursively
int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;  // Base case: not found
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) 
        return binarySearchRecursive(arr, target, mid + 1, right);
    else 
        return binarySearchRecursive(arr, target, left, mid - 1);
}

// Recursion depth analysis:
// Each call cuts search space in half
// n → n/2 → n/4 → n/8 → ... → 1
// How many times can you halve n before reaching 1?
// Answer: log₂(n) times
// 
// Time: O(log n) - max log n recursive calls, O(1) work per call
// Space: O(log n) - call stack depth = log n frames

Pattern 5: String Concatenation Trap

// SLOW: O(n²) time!
String result = "";
for (int i = 0; i < n; i++) {
    result += "a";  // Creates new string each time!
}

// Why O(n²)?
// Iteration 1: Copy 0 chars, add 1 = 1 operation
// Iteration 2: Copy 1 char, add 1 = 2 operations  
// Iteration 3: Copy 2 chars, add 1 = 3 operations
// ...
// Iteration n: Copy n-1 chars, add 1 = n operations
// Total: 1+2+3+...+n = n(n+1)/2 = O(n²)

// FAST: O(n) time!
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append("a");  // Appends to existing buffer, amortized O(1)
}
String result = sb.toString();  // O(n) final conversion

// Total: n × O(1) + O(n) = O(n)

int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

void logLoop(int n) {
    for (int i = 1; i < n; i = i * 2) {
        System.out.println(i);
    }
}

ArrayList list = new ArrayList<>();
for (int i = 0; i < n; i++) {
    list.add(i);  // What's the complexity of this single operation?
}

int power(int base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        int half = power(base, exp / 2);
        return half * half;
    } else {
        return base * power(base, exp - 1);
    }
}

// Method A
String result = "";
for (int i = 0; i < n; i++) {
    result += "a";
}

// Method B
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append("a");
}
String result = sb.toString();

O(1) Constant Space - In-Place

void swap(int[] arr, int i, int j) {
    int temp = arr[i];  // Only ONE extra variable
    arr[i] = arr[j];
    arr[j] = temp;
}

O(n) Linear Space - New Array

int[] copyArray(int[] arr) {
    int[] copy = new int[arr.length];  // Allocate n integers
    
    for (int i = 0; i < arr.length; i++) {
        copy[i] = arr[i];
    }
    
    return copy;
}

O(n) Linear Space - Recursion Stack

int factorial(int n) {
    if (n <= 1) return 1;  // Base case
    
    return n * factorial(n - 1);  // Each call waits for the next
}

// factorial(5) creates this call stack:
// factorial(5) waiting...
//   factorial(4) waiting...
//     factorial(3) waiting...
//       factorial(2) waiting...
//         factorial(1) returns 1

O(n²) Quadratic Space - 2D Array

int[][] createMatrix(int n) {
    return new int[n][n];  // n rows × n columns
}

// For n = 1000:
// 1000 × 1000 = 1,000,000 integers
// = 4,000,000 bytes = 4 MB

Common Space Complexity Patterns

Advanced Space Complexity Examples

Example 1: Stack Frame Visualization - Understanding Recursive Memory

// Recursive function to calculate sum
int recursiveSum(int n) {
    if (n == 0) return 0;
    return n + recursiveSum(n - 1);
}

// Call recursiveSum(5):
// 
// Memory Stack Visualization:
// ┌─────────────────────────────────┐
// │ recursiveSum(1) → n=1, return   │ ← 5th call (deepest)
// ├─────────────────────────────────┤
// │ recursiveSum(2) → n=2, waiting  │ ← 4th call
// ├─────────────────────────────────┤
// │ recursiveSum(3) → n=3, waiting  │ ← 3rd call
// ├─────────────────────────────────┤
// │ recursiveSum(4) → n=4, waiting  │ ← 2nd call
// ├─────────────────────────────────┤
// │ recursiveSum(5) → n=5, waiting  │ ← 1st call (original)
// └─────────────────────────────────┘
//
// Each box is a "stack frame" containing:
// - Parameter values (n)
// - Local variables
// - Return address (where to go back)
// - Typically 50-100 bytes each

int iterativeSum(int n) {
    int sum = 0;  // Only 2 variables in memory!
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}
// Space complexity: O(1) - only 2 variables, no matter how big n is!

Example 2: Hidden Space in String Building

// Approach 1: String concatenation (HIDDEN O(n²) space!)
String buildString(int n) {
    String result = "";
    for (int i = 0; i < n; i++) {
        result += "a";  // Each += creates a NEW string!
    }
    return result;
}

// Space complexity analysis:
// Iteration 1: Create new string of length 1 → 1 char allocated
// Iteration 2: Create new string of length 2 → 2 chars allocated (old 1 becomes garbage)
// Iteration 3: Create new string of length 3 → 3 chars allocated (old 2 becomes garbage)
// ...
// Total PEAK memory before garbage collection: 1+2+3+...+n = O(n²) space!
//
// Even after garbage collection, we created O(n²) temporary objects

// Approach 2: StringBuilder (O(n) space)
String buildStringEfficient(int n) {
    StringBuilder sb = new StringBuilder(n);  // Pre-allocate size n
    for (int i = 0; i < n; i++) {
        sb.append("a");  // Append to existing buffer
    }
    return sb.toString();
}

// Space complexity: O(n) - one buffer of size n, that's it!

Example 3: HashSet vs Array - Space Trade-offs

// Problem: Remove duplicates from array and return new array

// Approach 1: Using HashSet (O(n) time, O(n) space)
int[] removeDuplicatesHashSet(int[] arr) {
    Set set = new HashSet<>();  // O(n) space worst case
    for (int num : arr) {
        set.add(num);  // Stores each unique element
    }
    
    int[] result = new int[set.size()];  // O(k) space where k = unique count
    int i = 0;
    for (int num : set) {
        result[i++] = num;
    }
    return result;
    // Total space: O(n) for HashSet + O(k) for result ≤ O(n) + O(n) = O(n)
}

// Approach 2: Sort in-place (O(n log n) time, O(1) space if you can modify input)
int removeDuplicatesSorted(int[] arr) {
    if (arr.length == 0) return 0;
    
    Arrays.sort(arr);  // O(log n) space for merge sort, but we can use O(1) heap sort
    
    int j = 1;  // Pointer for unique elements
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[j++] = arr[i];  // Overwrite duplicates in-place
        }
    }
    return j;  // Number of unique elements (arr[0..j-1] has uniques)
    // Space: O(1) auxiliary - only 2 integer variables (i, j)
}

Example 4: Two Pointers - The O(1) Space Hero

// Problem: Reverse a string in-place

// GOOD: Two pointers O(1) space
void reverseStringInPlace(char[] s) {
    int left = 0, right = s.length - 1;  // Just 2 integer variables!
    
    while (left < right) {
        // Swap s[left] and s[right]
        char temp = s[left];  // 1 char variable
        s[left] = s[right];
        s[right] = temp;
        
        left++;
        right--;
    }
}
// Space: O(1) - only 3 variables (left, right, temp)
// No matter if array has 10 or 10 million characters!

// BAD: Creating new array O(n) space
char[] reverseStringNewArray(char[] s) {
    char[] reversed = new char[s.length];  // O(n) space!
    
    for (int i = 0; i < s.length; i++) {
        reversed[i] = s[s.length - 1 - i];
    }
    return reversed;
}
// Space: O(n) - allocates a whole new array

Example 5: Dynamic Programming - Trading Space for Speed

// Problem: Nth Fibonacci number

// Approach 1: Naive recursion (O(2^n) time, O(n) space)
int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// Time: O(2^n) - exponential! fib(40) = 102,334,155 calls!
// Space: O(n) - recursion depth at most n

// Approach 2: Memoization (O(n) time, O(n) space)
int fibMemo(int n, Map memo) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    
    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result);
    return result;
}
// Time: O(n) - each number computed once, then cached
// Space: O(n) for HashMap + O(n) for recursion stack = O(n)

// Approach 3: Tabulation (O(n) time, O(n) space, no recursion)
int fibTable(int n) {
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// Time: O(n) - single loop
// Space: O(n) - array of size n+1

// Approach 4: Optimized iteration (O(n) time, O(1) space!)
int fibOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;  // Only track last 2 values!
    
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
// Time: O(n) - single loop
// Space: O(1) - only 3 variables!

void reverseArray(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Method A: HashSet
boolean hasDuplicateA(int[] arr) {
    Set seen = new HashSet<>();
    for (int num : arr) {
        if (!seen.add(num)) return true;
    }
    return false;
}

// Method B: Sort first
boolean hasDuplicateB(int[] arr) {
    Arrays.sort(arr);
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i-1]) return true;
    }
    return false;
}

// Fibonacci with full DP array
int fibTable(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// Optimized Fibonacci
int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int[][] createMatrix(int n) {
    return new int[n][n];
}

// How much memory for n = 10,000?

// Example: Find if array has duplicate
boolean hasDuplicate(int[] arr) {
    // Method 1: Brute Force - O(n²) time, O(1) space
    for (int i = 0; i < arr.length; i++) {      // n iterations
        for (int j = i + 1; j < arr.length; j++) { // ~n iterations
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
    
    // Method 2: Using HashSet - O(n) time, O(n) space
    Set seen = new HashSet<>();  // O(n) space
    for (int num : arr) {                  // O(n) iterations
        if (!seen.add(num)) return true;   // O(1) lookup
    }
    return false;
    
    // Method 3: Sort First - O(n log n) time, O(1) space
    Arrays.sort(arr);                      // O(n log n)
    for (int i = 1; i < arr.length; i++) { // O(n)
        if (arr[i] == arr[i - 1]) return true;
    }
    return false;
}

Comparison Table

Deep Dive: 15 More Code Analysis Examples

Let's analyze various code patterns you'll encounter. For each example, identify: time complexity, space complexity, and why.

Example 1 Contains Duplicate Value

// Check if array contains any duplicate values
boolean containsDuplicate(int[] nums) {
    Set seen = new HashSet<>();
    for (int num : nums) {
        if (seen.contains(num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

Example 2 First Unique Character

// Find index of first non-repeating character
int firstUniqChar(String s) {
    // Step 1: Count frequencies
    Map freq = new HashMap<>();
    for (char c : s.toCharArray()) {  // O(n)
        freq.put(c, freq.getOrDefault(c, 0) + 1);
    }
    
    // Step 2: Find first unique
    for (int i = 0; i < s.length(); i++) {  // O(n)
        if (freq.get(s.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

Example 3 Group Anagrams

// Group strings that are anagrams
List> groupAnagrams(String[] strs) {
    Map> map = new HashMap<>();
    
    for (String str : strs) {  // O(n) strings
        char[] chars = str.toCharArray();  // O(k)
        Arrays.sort(chars);  // O(k log k) where k = string length
        String sorted = new String(chars);  // O(k)
        
        if (!map.containsKey(sorted)) {
            map.put(sorted, new ArrayList<>());
        }
        map.get(sorted).add(str);  // O(1)
    }
    
    return new ArrayList<>(map.values());
}

Example 4 Product of Array Except Self

// Calculate product of all elements except current
int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    
    // Left products: result[i] = product of all to left of i
    result[0] = 1;
    for (int i = 1; i < n; i++) {  // O(n)
        result[i] = result[i - 1] * nums[i - 1];
    }
    
    // Right products: multiply by product of all to right
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {  // O(n)
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}

Example 5 Maximum Subarray Sum (Kadane's Algorithm)

// Find contiguous subarray with maximum sum
int maxSubArray(int[] nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    
    for (int i = 1; i < nums.length; i++) {  // O(n)
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

Example 6 Spiral Matrix Traversal

// Print matrix in spiral order
List spiralOrder(int[][] matrix) {
    List result = new ArrayList<>();
    if (matrix.length == 0) return result;
    
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {  // O(m×n)
        // Traverse right
        for (int i = left; i <= right; i++) result.add(matrix[top][i]);
        top++;
        
        // Traverse down
        for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
        right--;
        
        // Traverse left
        if (top <= bottom) {
            for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
            bottom--;
        }
        
        // Traverse up
        if (left <= right) {
            for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
            left++;
        }
    }
    
    return result;
}

Example 7 Rotate Matrix 90 Degrees

// Rotate n×n matrix 90 degrees clockwise in-place
void rotate(int[][] matrix) {
    int n = matrix.length;
    
    // Step 1: Transpose (swap across diagonal)
    for (int i = 0; i < n; i++) {  // O(n)
        for (int j = i; j < n; j++) {  // O(n) but j starts at i
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    
    // Step 2: Reverse each row
    for (int i = 0; i < n; i++) {  // O(n)
        for (int j = 0; j < n / 2; j++) {  // O(n/2)
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
}

Example 8 Longest Palindromic Substring

// Find longest palindromic substring
String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    
    int start = 0, end = 0;
    
    for (int i = 0; i < s.length(); i++) {  // O(n)
        int len1 = expandAroundCenter(s, i, i);       // Odd length
        int len2 = expandAroundCenter(s, i, i + 1);   // Even length
        int len = Math.max(len1, len2);
        
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    
    return s.substring(start, end + 1);
}

int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && 
           s.charAt(left) == s.charAt(right)) {  // O(n) worst case
        left--;
        right++;
    }
    return right - left - 1;
}

Example 9 Three Sum

// Find all triplets that sum to zero
List> threeSum(int[] nums) {
    List> result = new ArrayList<>();
    Arrays.sort(nums);  // O(n log n)
    
    for (int i = 0; i < nums.length - 2; i++) {  // O(n)
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // Skip duplicates
        
        int left = i + 1, right = nums.length - 1;
        while (left < right) {  // O(n) worst case
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

Example 10 Word Ladder (BFS)

// Find shortest transformation from beginWord to endWord
int ladderLength(String beginWord, String endWord, List wordList) {
    Set wordSet = new HashSet<>(wordList);  // O(n)
    if (!wordSet.contains(endWord)) return 0;
    
    Queue queue = new LinkedList<>();
    queue.offer(beginWord);
    int level = 1;
    
    while (!queue.isEmpty()) {  // O(n) words
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String current = queue.poll();
            if (current.equals(endWord)) return level;
            
            char[] chars = current.toCharArray();
            for (int j = 0; j < chars.length; j++) {  // O(L) word length
                char original = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {  // O(26) = O(1)
                    chars[j] = c;
                    String newWord = new String(chars);
                    
                    if (wordSet.contains(newWord)) {
                        queue.offer(newWord);
                        wordSet.remove(newWord);  // Mark visited
                    }
                }
                chars[j] = original;  // Restore
            }
        }
        level++;
    }
    
    return 0;
}

// Method A: Brute Force
int[] twoSumBrute(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] {i, j};
            }
        }
    }
    return new int[] {-1, -1};
}

// Method B: HashMap
int[] twoSumHash(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[] {-1, -1};
}

boolean isValid(String s) {
    Stack stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

int longestConsecutive(int[] nums) {
    Set numSet = new HashSet<>();
    for (int num : nums) numSet.add(num);
    
    int longest = 0;
    for (int num : numSet) {
        if (!numSet.contains(num - 1)) {  // Only start of sequence
            int currentNum = num;
            int streak = 1;
            while (numSet.contains(currentNum + 1)) {
                currentNum++;
                streak++;
            }
            longest = Math.max(longest, streak);
        }
    }
    return longest;
}

// Test case: nums = [100, 4, 200, 1, 3, 2]
// Expected output: 4 (sequence: 1, 2, 3, 4)

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue minHeap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );
    
    for (ListNode list : lists) {
        if (list != null) minHeap.offer(list);
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode smallest = minHeap.poll();
        current.next = smallest;
        current = current.next;
        if (smallest.next != null) {
            minHeap.offer(smallest.next);
        }
    }
    return dummy.next;
}

// Given: k = 3 lists, N = total nodes across all lists
// lists[0]: 1 → 4 → 5
// lists[1]: 1 → 3 → 4
// lists[2]: 2 → 6

int[] maxSlidingWindow(int[] nums, int k) {
    Deque deque = new ArrayDeque<>();  // Stores indices
    int[] result = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside current window
        while (!deque.isEmpty() && deque.peek() < i - k + 1) {
            deque.poll();
        }
        // Remove smaller elements (they can never be max)
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offer(i);
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peek()];
        }
    }
    return result;
}

// Test: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
// Output: [3, 3, 5, 5, 6, 7]