Must-Know Array DSA Topics with Time & Space Complexity

Below is a comprehensive list of must-know Array DSA topics, including time & space complexity for common operations.

---

🔹 Basic Array Operations

Operation	Time Complexity	Space Complexity	Description
Access Element	O(1)	O(1)	Direct index access.
Update Element	O(1)	O(1)	Directly modifying an element at an index.
Insert at End	O(1) (Amortized)	O(1)	Only for dynamic arrays.
Insert at Beginning / Middle	O(n)	O(1)	Needs shifting of elements.
Delete at End	O(1)	O(1)	Removes last element.
Delete at Beginning / Middle	O(n)	O(1)	Needs shifting of elements.
Search (Unsorted)	O(n)	O(1)	Linear search.
Search (Sorted)	O(log n)	O(1)	Binary search (divide & conquer).
Sort Array	O(n log n)	O(1) or O(n)	Merge Sort or Quick Sort.

---

🔹 Substring, Subsequence & Related Patterns

Substring vs Subsequence vs Subarray vs Other Array Concepts

These terms are often confused in data structures & algorithms (DSA), so let’s break them down with definitions, examples, and properties.

---

🔹 1. Substring

Definition:

A substring is a continuous part of a string. It must maintain contiguous characters in the same order.

Example:

For the string “abcde”, some substrings are:

• "abc" ✅ (Valid)
• "bcd" ✅ (Valid)
• "ace" ❌ (Invalid, non-contiguous)

Properties:

• Order matters ✅
• Contiguous characters ✅
• Number of substrings: ( O(n^2) ) (including single characters)
• Operations: Can be extracted using s.substring(start, end)

Code (Java):

public class SubstringExample {
    public static void main(String[] args) {
        String str = "abcde";
        System.out.println(str.substring(1, 4)); // "bcd"
    }
}

🔹 Brute Force:

• Generate all substrings using nested loops.
• Time Complexity: O(n2)O(n2)
• Space Complexity: O(1)O(1)

javaCopyEdit// Brute Force - Generate all substrings
public class SubstringBruteForce {
    public static void main(String[] args) {
        String str = "abc";
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j <= str.length(); j++) {
                System.out.println(str.substring(i, j));
            }
        }
    }
}

🔹 Optimal Approach:

• Sliding Window (For problems like Longest Unique Substring)
• Time Complexity: O(n)O(n) (for some problems like Longest Unique Substring)
• Space Complexity: O(1)O(1)

---

🔹 2. Subsequence

Definition:

A subsequence is a sequence derived by removing some or no characters from a string without changing their order.

Example:

For the string “abcde”, some subsequences are:

• "abc" ✅ (Valid)
• "ace" ✅ (Valid)
• "edc" ❌ (Invalid, order changed)

Properties:

• Order matters ✅
• Contiguous characters NOT required ❌
• Number of subsequences: ( 2^n ) (Each character can either be included or excluded)
• Operations: Typically solved using recursion or dynamic programming (e.g., LCS – Longest Common Subsequence)

Code (Java – Generate Subsequences)

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

public class Subsequences {
    public static void generateSubsequences(String str, int index, String curr, List<String> result) {
        if (index == str.length()) {
            result.add(curr);
            return;
        }
        generateSubsequences(str, index + 1, curr + str.charAt(index), result); // Include
        generateSubsequences(str, index + 1, curr, result); // Exclude
    }

    public static void main(String[] args) {
        List<String> result = new ArrayList<>();
        generateSubsequences("abc", 0, "", result);
        System.out.println(result);
    }
}

Output: [abc, ab, ac, a, bc, b, c, ""] (Total: ( 2^3 = 8 ))

🔹 Brute Force:

• Generate all subsequences using recursion.
• Time Complexity: O(2n)O(2n)
• Space Complexity: O(n)O(n) (recursion stack)

🔹 Optimal Approach:

Space Complexity: O(n)O(n)

Dynamic Programming (LIS, LCS, etc.)

Time Complexity: O(n2)O(n2) (for Longest Increasing Subsequence using DP)

📌 Common Problems:

• Longest Increasing Subsequence (LIS)
• Brute Force → O(2ⁿ)
• DP (O(n²)), Binary Search (O(n log n))
• Subset Sum / Combination Sum
• Recursion → O(2ⁿ)
• DP → O(n * sum)
• Longest Common Subsequence (LCS)
• DP → O(n * m)

---

🔹 3. Subarray

Definition:

A subarray is a continuous part of an array.

Example:

For the array [1, 2, 3, 4], some subarrays are:

• [1, 2] ✅ (Valid)
• [2, 3, 4] ✅ (Valid)
• [1, 3] ❌ (Invalid, non-contiguous)

Properties:

• Order matters ✅
• Contiguous elements only ✅
• Number of subarrays: ( O(n^2) )
• Common problems: Kadane’s Algorithm (Maximum Sum Subarray)

🔹 Brute Force:

• Generate all subarrays using nested loops.
• Time Complexity: O(n2)O(n2)
• Space Complexity: O(1)O(1)

Code (Java – Generate All Subarrays)

public class SubarrayExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                for (int k = i; k <= j; k++) {
                    System.out.print(arr[k] + " ");
                }
                System.out.println();
            }
        }
    }
}

Output (All Subarrays of [1,2,3,4]):

1 
1 2 
1 2 3 
1 2 3 4 
2 
2 3 
2 3 4 
3 
3 4 
4 

🔹 Optimal Approach:

• Kadane’s Algorithm (Maximum Sum Subarray)
• Time Complexity: O(n)O(n)
• Space Complexity: O(1)O(1)

javaCopyEditpublic class KadaneAlgorithm {
    public static int maxSubarraySum(int[] arr) {
        int maxSum = Integer.MIN_VALUE, currSum = 0;
        for (int num : arr) {
            currSum = Math.max(num, currSum + num);
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubarraySum(arr)); // Output: 6
    }
}

Code (Java – Generate All Subarrays)

📌 Common Problems:

• Kadane’s Algorithm (Max Sum Subarray) → O(n)
• Prefix Sum (Range Sum Queries) → O(n) precompute, O(1) query
• Sliding Window (Fixed/Variable Window) → O(n)

---

🔹 4. Subset

Definition:

A subset is any possible selection of elements from an array in any order.

Example:

For the array [1, 2, 3], some subsets are:

• [] ✅ (Empty subset)
• [1] ✅
• [2, 3] ✅
• [3, 1] ✅ (Order doesn’t matter)
• [1, 3, 2] ✅ (Also valid)

Properties:

• Order does NOT matter ❌
• Contiguity NOT required ❌
• Number of subsets: ( 2^n ) (Same as subsequences)
• Common problems: Subset Sum, Power Set

🔹 Brute Force:

Space Complexity: O(n)O(n) (recursion stack)

Generate all subsets using recursion.

Time Complexity: O(2n)O(2n)

import java.util.*;

public class SubsetExample {
    public static void generateSubsets(int[] arr, int index, List<Integer> current, List<List<Integer>> result) {
        if (index == arr.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        generateSubsets(arr, index + 1, current, result); // Exclude
        current.add(arr[index]);
        generateSubsets(arr, index + 1, current, result); // Include
        current.remove(current.size() - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        generateSubsets(arr, 0, new ArrayList<>(), result);
        System.out.println(result);
    }
}

Output: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

🔹 Optimal Approach:

• Bit Manipulation (Power Set)
• Time Complexity: O(2n)O(2n) (No way to improve beyond brute force)
• Space Complexity: O(1)O(1) (If only printing subsets)

javaCopyEditimport java.util.*;

public class SubsetBitManipulation {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int n = arr.length;
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < (1 << n); i++) { // 2^n subsets
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) { // Check if jth bit is set
                    subset.add(arr[j]);
                }
            }
            result.add(subset);
        }
        System.out.println(result);
    }
}

---

🔹 Key Differences Table

Concept	Contiguous Required?	Order Matters?	Total Count
Substring	✅ Yes	✅ Yes	( O(n^2) )
Subsequence	❌ No	✅ Yes	( 2^n )
Subarray	✅ Yes	✅ Yes	( O(n^2) )
Subset	❌ No	❌ No	( 2^n )

---

🔹 Practical Use Cases

Problem Type	Common Approach
Find max sum subarray	Kadane’s Algorithm
Longest increasing subsequence	Dynamic Programming (LIS)
Find all subsets (power set)	Backtracking/Bit Manipulation
Find all subarrays	Nested loops or sliding window
Check if one string is a subsequence of another	Two-pointer technique

---

✅ Summary

• Substring = Continuous part of a string (O(n²))
• Subsequence = Any order-preserved sequence (O(2ⁿ))
• Subarray = Continuous part of an array (O(n²))
• Subset = Any selection of elements (O(2ⁿ))

---

🔹 Patterns in Arrays

1️⃣ Prefix Sum

📌 Pattern: Precompute cumulative sums to answer range sum queries in O(1) time.

🔹 Use Cases:

• Range Sum Query (O(n) precompute, O(1) query)
• Product of Array Except Self (O(n) time, O(1) space)
• Find equilibrium index (where left sum = right sum)

---

2️⃣ Sliding Window (Fixed & Variable)

📌 Pattern: Maintain a window & expand/shrink based on conditions.

🔹 Use Cases:

• Fixed-size window (e.g., max sum of subarray of size k) → O(n)
• Variable-size window (e.g., smallest subarray sum ≥ target) → O(n)

---

3️⃣ Two Pointers

📌 Pattern: Use two indices to reduce search space efficiently.

🔹 Use Cases:

• Sorted Array Two Sum (O(n))
• 3Sum / 4Sum (O(n²))
• Container with Most Water (O(n))

---

4️⃣ Binary Search on Arrays

📌 Pattern: Search in a sorted array efficiently in O(log n).

🔹 Use Cases:

• Find first/last occurrence of element
• Find peak element
• Binary Search on Answers (e.g., Minimize Maximum Distance, Split Array)

---

🔹 Must-Know Problems

Problem	Approach	Time Complexity
Two Sum	Hash Map	O(n)
3Sum	Sorting + Two Pointers	O(n²)
Maximum Subarray (Kadane’s)	DP	O(n)
Longest Consecutive Sequence	HashSet	O(n)
Product of Array Except Self	Prefix/Suffix	O(n)
Minimum Window Substring	Sliding Window	O(n)
Trapping Rain Water	Two Pointers	O(n)

---

Here are Java code examples for common array operations:

🔹 Array Util Java Methods:

Arrays.sort(numbers);

int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);

int[] rangeCopy = Arrays.copyOfRange(originalArray, 1, 4); // Copies elements from index 1 (inclusive) to 4 (exclusive)

java.util.List<Integer> numberList = Arrays.asList(5, 2, 8, 1, 9, 4);

boolean isEqual = Arrays.equals(numbers, numbers2);

int index = Arrays.binarySearch(numbers, 4);

Arrays.fill(numbers, 0);

---

🔹 Basic Array Operations

1️⃣ Access, Update, Insert & Delete

import java.util.Arrays;

public class ArrayOperations {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};

        // Access
        System.out.println("Element at index 2: " + arr[2]); // O(1)

        // Update
        arr[2] = 100; // O(1)
        System.out.println("Updated array: " + Arrays.toString(arr));

        // Insert at the end
        arr = Arrays.copyOf(arr, arr.length + 1); // O(1) amortized
        arr[arr.length - 1] = 60;
        System.out.println("Array after inserting 60: " + Arrays.toString(arr));

        // Insert at index 2 (shifting elements)
        int insertIndex = 2;
        int insertValue = 99;
        arr = Arrays.copyOf(arr, arr.length + 1);
        System.arraycopy(arr, insertIndex, arr, insertIndex + 1, arr.length - insertIndex - 1);
        arr[insertIndex] = insertValue; // O(n)
        System.out.println("Array after inserting 99 at index 2: " + Arrays.toString(arr));

        // Delete element at index 3
        int deleteIndex = 3;
        System.arraycopy(arr, deleteIndex + 1, arr, deleteIndex, arr.length - deleteIndex - 1);
        arr = Arrays.copyOf(arr, arr.length - 1); // O(n)
        System.out.println("Array after deleting element at index 3: " + Arrays.toString(arr));
    }
}

---

🔹 Searching in an Array

1️⃣ Linear Search (Unsorted)

public class LinearSearch {
    public static int search(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i; // O(n)
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 7, 1, 9, 5};
        System.out.println("Element found at index: " + search(arr, 9));
    }
}

2️⃣ Binary Search (Sorted)

import java.util.Arrays;

public class BinarySearch {
    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;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // O(log n)
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        System.out.println("Element found at index: " + binarySearch(arr, 5));
    }
}

---

🔹 Prefix Sum (Range Sum)

public class PrefixSum {
    public static int[] prefixSum(int[] arr) {
        int[] prefix = new int[arr.length];
        prefix[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefix[i] = prefix[i - 1] + arr[i]; // O(n)
        }
        return prefix;
    }

    public static int rangeSum(int[] prefix, int left, int right) {
        if (left == 0) return prefix[right];
        return prefix[right] - prefix[left - 1]; // O(1)
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 1, 6};
        int[] prefix = prefixSum(arr);
        System.out.println("Sum of range [1,3]: " + rangeSum(prefix, 1, 3));
    }
}

---

🔹 Sliding Window (Max Sum Subarray of Fixed Size K)

public class SlidingWindow {
    public static int maxSumSubarray(int[] arr, int k) {
        int maxSum = 0, windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];

        maxSum = windowSum;
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k]; // O(n)
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Max sum of 3-size subarray: " + maxSumSubarray(arr, 3));
    }
}

---

🔹 Two Pointer (Pair Sum)

import java.util.Arrays;

public class TwoPointer {
    public static boolean twoSum(int[] arr, int target) {
        Arrays.sort(arr); // O(n log n)
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) return true;
            else if (sum < target) left++;
            else right--;
        }
        return false; // O(n)
    }

    public static void main(String[] args) {
        int[] arr = {4, 1, 6, 3, 8};
        System.out.println("Pair exists: " + twoSum(arr, 9));
    }
}

---

🔹 Kadane’s Algorithm (Max Subarray Sum)

public class Kadane {
    public static int maxSubarraySum(int[] arr) {
        int maxSum = arr[0], currentSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum); // O(n)
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max Subarray Sum: " + maxSubarraySum(arr));
    }
}

---

🔹 Product of Array Except Self (O(n) Time, O(1) Space)

import java.util.Arrays;

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, 1);

        int leftProduct = 1, rightProduct = 1;
        for (int i = 0; i < n; i++) {
            result[i] *= leftProduct;
            leftProduct *= arr[i]; // Prefix product
        }
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= arr[i]; // Suffix product
        }
        return result; // O(n) time, O(1) space
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        System.out.println("Product Except Self: " + Arrays.toString(productExceptSelf(arr)));
    }
}

---

✅ Summary

✅ Basic Operations: Insert, Delete, Search
✅ Sorting & Searching: Binary Search, Merge/Quick Sort
✅ Patterns: Prefix Sum, Sliding Window, Two Pointers
✅ Advanced Algorithms: Kadane’s Algorithm, Product Except Self