🧠 Master DSA for Interviews — Arrays

Your zero-to-hero guide for mastering Arrays in Java — built for coding interviews and DSA preparation.

Arrays are the #1 topic in technical interviews. Every major pattern — sliding window, two pointers, prefix sums, Kadane's — lives on top of arrays. Mastering them gives you the mental model to crack Easy problems confidently and unlock Medium/Hard ones systematically. This repo walks you from memory layout to optimized interview solutions, all in Java.

🏷️ Badges

📦 Basics of Arrays

An array is a contiguous block of memory storing elements of the same type, accessed via zero-based index in O(1).

Property	Static Array	Dynamic Array (`ArrayList`)
Size	Fixed at declaration	Grows automatically
Memory	Stack or Heap	Heap
Resize	❌ Not possible	✅ Doubles capacity

Memory Layout

Index:  [0]   [1]   [2]   [3]   [4]
Value:  [10]  [20]  [30]  [40]  [50]
Addr:  1000  1004  1008  1012  1016   ← each int = 4 bytes

Java Example

// Static Array
int[] staticArr = new int[5];
staticArr[0] = 10;

int[] preloaded = {10, 20, 30, 40, 50};

// Dynamic Array
import java.util.ArrayList;
ArrayList<Integer> dynamicArr = new ArrayList<>();
dynamicArr.add(10);
dynamicArr.add(20);
dynamicArr.remove(Integer.valueOf(10)); // removes by value

⏱️ Time & Space Complexity

Operation	Static Array	Dynamic Array	Reason
Access by index	O(1)	O(1)	Direct memory offset calculation
Search (unsorted)	O(n)	O(n)	Must scan every element
Search (sorted)	O(log n)	O(log n)	Binary search
Insert at end	O(1)	O(1) amortized	Direct placement / occasional resize
Insert at index	O(n)	O(n)	Shift elements right
Delete at index	O(n)	O(n)	Shift elements left
Space	O(n)	O(n)	One slot per element

💡 Tip: Dynamic arrays double in size on resize, making the amortized insert O(1). But worst-case is O(n) — keep this in mind for real-time systems.

⚙️ Common Array Operations

Traversal

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++)
        System.out.print(arr[i] + " ");
}

Linear Search

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++)
        if (arr[i] == target) return i;
    return -1;
}

Binary Search (sorted array)

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

Insertion at Index

int[] insertAt(int[] arr, int idx, int val) {
    int[] result = new int[arr.length + 1];
    for (int i = 0; i < idx; i++) result[i] = arr[i];
    result[idx] = val;
    for (int i = idx; i < arr.length; i++) result[i + 1] = arr[i];
    return result;
}

Deletion at Index

int[] deleteAt(int[] arr, int idx) {
    int[] result = new int[arr.length - 1];
    for (int i = 0, j = 0; i < arr.length; i++)
        if (i != idx) result[j++] = arr[i];
    return result;
}

🧩 Important Array Patterns for DSA

1. Two Pointer

Intuition: Use two indices moving toward/away from each other to avoid nested loops. Use-case: Pair sum, palindrome check, container with most water.

// Check if sorted array has pair summing to target
boolean twoSum(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int sum = arr[l] + arr[r];
        if (sum == target) return true;
        else if (sum < target) l++;
        else r--;
    }
    return false;
}

2. Sliding Window

Intuition: Maintain a window of size k; slide it right, adding new and removing old in O(1). Use-case: Max sum subarray of size k, longest substring without repeats.

int maxSumWindow(int[] arr, int k) {
    int sum = 0, max = 0;
    for (int i = 0; i < k; i++) sum += arr[i];
    max = sum;
    for (int i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k];
        max = Math.max(max, sum);
    }
    return max;
}

3. Prefix Sum

Intuition: Precompute cumulative sums so range queries become O(1). Use-case: Subarray sum equals K, range sum queries.

int[] buildPrefix(int[] arr) {
    int[] prefix = new int[arr.length + 1];
    for (int i = 0; i < arr.length; i++)
        prefix[i + 1] = prefix[i] + arr[i];
    return prefix;
}
// Sum from index l to r (inclusive):  prefix[r+1] - prefix[l]

4. Kadane's Algorithm

Intuition: At each index, decide: extend the current subarray or start fresh. Use-case: Maximum subarray sum.

int kadane(int[] arr) {
    int maxSum = arr[0], curr = arr[0];
    for (int i = 1; i < arr.length; i++) {
        curr = Math.max(arr[i], curr + arr[i]);
        maxSum = Math.max(maxSum, curr);
    }
    return maxSum;
}

5. Hashing with Arrays

Intuition: Use a frequency/count array (or HashMap) to track seen elements in O(1). Use-case: Two Sum, find duplicates, anagram check.

boolean hasDuplicate(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    for (int x : arr)
        if (!seen.add(x)) return true;
    return false;
}

🏆 Top Interview Problems

1. Two Sum

Problem: Return indices of two numbers that add up to target. Pattern: HashMap (value → index)

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int comp = target - nums[i];
        if (map.containsKey(comp)) return new int[]{map.get(comp), i};
        map.put(nums[i], i);
    }
    return new int[]{};
}

Time	Space
O(n)	O(n)

2. Best Time to Buy & Sell Stock

Problem: Find max profit from one buy-sell transaction. Pattern: Track running minimum price.

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        maxProfit = Math.max(maxProfit, p - minPrice);
    }
    return maxProfit;
}

Time	Space
O(n)	O(1)

3. Maximum Subarray

Problem: Find contiguous subarray with the largest sum. Pattern: Kadane's Algorithm.

int maxSubArray(int[] nums) {
    int max = nums[0], curr = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        max = Math.max(max, curr);
    }
    return max;
}

Time	Space
O(n)	O(1)

4. Move Zeroes

Problem: Move all 0s to end, maintaining order of non-zero elements. Pattern: Two Pointer (write pointer).

void moveZeroes(int[] nums) {
    int writeIdx = 0;
    for (int n : nums) if (n != 0) nums[writeIdx++] = n;
    while (writeIdx < nums.length) nums[writeIdx++] = 0;
}

Time	Space
O(n)	O(1)

5. Rotate Array

Problem: Rotate array to the right by k steps. Pattern: Triple reverse.

void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}
void reverse(int[] nums, int l, int r) {
    while (l < r) { int t = nums[l]; nums[l++] = nums[r]; nums[r--] = t; }
}

Time	Space
O(n)	O(1)

6. Product of Array Except Self

Problem: Return array where each element is the product of all others (no division). Pattern: Prefix & Suffix product pass.

int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) res[i] = res[i-1] * nums[i-1];
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) { res[i] *= suffix; suffix *= nums[i]; }
    return res;
}

Time	Space
O(n)	O(1) output

7. Merge Sorted Arrays

Problem: Merge nums2 into nums1 (in-place). nums1 has extra space. Pattern: Two Pointer from the end.

void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0)
        nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
    while (j >= 0) nums1[k--] = nums2[j--];
}

Time	Space
O(m+n)	O(1)

8. Trapping Rain Water

Problem: Calculate total water trapped between bars. Pattern: Two Pointer with max-left / max-right tracking.

int trap(int[] height) {
    int l = 0, r = height.length - 1, maxL = 0, maxR = 0, water = 0;
    while (l < r) {
        if (height[l] <= height[r]) {
            maxL = Math.max(maxL, height[l]);
            water += maxL - height[l++];
        } else {
            maxR = Math.max(maxR, height[r]);
            water += maxR - height[r--];
        }
    }
    return water;
}

Time	Space
O(n)	O(1)

⚠️ Edge Cases to Remember

Empty array — always check arr.length == 0 before any logic.
Single element — loops may not execute; ensure the answer still returns correctly.
All negative numbers — Kadane's must still return the least-negative element.
k ≥ n (rotate/window) — always apply k %= n to avoid index out of bounds.
Integer overflow — use long when summing large values (e.g., product problems).
Duplicate elements — HashSet/HashMap logic must account for repeated values.
Already sorted input — some O(n log n) solutions become trivially O(n).
Array of size 2 — boundary cases for two-pointer problems.
Negative indices — Java doesn't support them; validate user-supplied indices.
Off-by-one errors — be precise with < vs <= in loop bounds and binary search.

🎨 Visualization Examples

Sliding Window (size k=3)

arr = [2, 1, 5, 1, 3, 2],  k = 3

Step 1:  [2  1  5] 1  3  2   → sum = 8
Step 2:   2 [1  5  1] 3  2   → sum = 7  (add 1, remove 2)
Step 3:   2  1 [5  1  3] 2   → sum = 9  (add 3, remove 1)  ← MAX
Step 4:   2  1  5 [1  3  2]  → sum = 6  (add 2, remove 5)

Two-Pointer Reversal

arr = [1, 2, 3, 4, 5]
       L           R

Step 1: swap(1,5) → [5, 2, 3, 4, 1],  L++, R--
Step 2: swap(2,4) → [5, 4, 3, 2, 1],  L++, R--
Step 3: L >= R → STOP ✅

Kadane's Algorithm Walk-through

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

idx:    0   1   2   3   4   5   6   7   8
curr:  -2   1  -2   4   3   5   6   1   5
max:   -2   1   1   4   4   5   6   6   6   ← Answer: 6
                     ↑ reset point (arr[i] > curr+arr[i])

📝 Practice Problems

#	Problem	Link	Difficulty	Pattern
1	Two Sum	LC #1	🟢 Easy	Hashing
2	Best Time to Buy & Sell Stock	LC #121	🟢 Easy	Greedy / Min tracking
3	Contains Duplicate	LC #217	🟢 Easy	HashSet
4	Move Zeroes	LC #283	🟢 Easy	Two Pointer
5	Maximum Subarray	LC #53	🟡 Medium	Kadane's
6	Product of Array Except Self	LC #238	🟡 Medium	Prefix/Suffix
7	Subarray Sum Equals K	LC #560	🟡 Medium	Prefix Sum + HashMap
8	Rotate Array	LC #189	🟡 Medium	Triple Reverse
9	3Sum	LC #15	🟡 Medium	Two Pointer + Sort
10	Merge Intervals	LC #56	🟡 Medium	Sorting + Greedy
11	Trapping Rain Water	LC #42	🔴 Hard	Two Pointer
12	First Missing Positive	LC #41	🔴 Hard	Index as hash
13	Median of Two Sorted Arrays	LC #4	🔴 Hard	Binary Search
14	Sliding Window Maximum	LC #239	🔴 Hard	Deque / Monotonic

🚫 Common Mistakes & How to Avoid Them

Off-by-one in loops — Always double-check i < n vs i <= n; draw a small example.
Not handling empty arrays — Add if (arr == null || arr.length == 0) return ... at the top.
Forgetting k %= n for rotations — k could be larger than array size; always normalize.
Using int when long is needed — Multiplication of large values overflows; cast early.
Modifying array while iterating — Use a separate write pointer or result array.
Assuming sorted input — Read the problem constraints carefully before picking binary search.
Wrong binary search boundary — Use lo + (hi - lo) / 2 to prevent overflow; test with 2 elements.
HashMap collision confusion — map.get(key) returns null if absent; use getOrDefault.
Sliding window with variable size — Shrink the window when a constraint is violated; don't just expand.
Not considering duplicates in two-pointer problems — Skip duplicate values after each match to avoid repeated pairs.

🚀 How to Use This Repo

# 1. Clone the repository
git clone https://github.com/MasterDSA/arrays-java.git
cd arrays-java

# 2. Navigate to a topic
cd src/arrays/twopointer/

# 3. Compile and run
javac Main.java
java Main

# 4. Run all solutions at once (if Makefile provided)
make run

Folder structure:

arrays-java/
├── src/
│   └── arrays/
│       ├── basics/         ← Array fundamentals
│       ├── twopointer/     ← Two-pointer problems
│       ├── slidingwindow/  ← Sliding window problems
│       ├── prefixsum/      ← Prefix sum problems
│       └── topproblems/    ← All 8 interview classics
├── solutions/              ← Optimized solutions with comments
└── README.md

📌 Note: Each folder contains a Problem.md explaining the problem, a Solution.java with the optimized answer, and a BruteForce.java for comparison.

🤝 Contributing

Contributions are welcome! Please follow these steps:

Fork this repository.
Create a feature branch: git checkout -b feat/add-sliding-window-problem
Write your solution in Java 17.
Compile with javac YourSolution.java — no warnings allowed.
Add at least 3 test cases (including edge cases).
Submit a Pull Request with a clear description of what was added.

Code style guidelines:

Use camelCase for variables and methods.
Add a // Time: O(...) Space: O(...) comment above every solution method.
Keep methods under 30 lines; extract helpers when needed.

📄 License

This project is licensed under the MIT License — see the LICENSE file for details.

MIT License © 2024 MasterDSA
Permission is hereby granted, free of charge, to any person obtaining a copy of this software...

⭐ If this repo helped you crack an interview, give it a star! ⭐
Built with ❤️ for every developer on their DSA journey.

Name		Name	Last commit message	Last commit date
Latest commit History 4 Commits
README.md		README.md
README2.md		README2.md
index.html		index.html

Folders and files

Latest commit

History

Repository files navigation

🧠 Master DSA for Interviews — Arrays

🏷️ Badges

📚 Table of Contents

📦 Basics of Arrays

Memory Layout

Java Example

⏱️ Time & Space Complexity

⚙️ Common Array Operations

Traversal

Linear Search

Binary Search (sorted array)

Insertion at Index

Deletion at Index

🧩 Important Array Patterns for DSA

1. Two Pointer

2. Sliding Window

3. Prefix Sum

4. Kadane's Algorithm

5. Hashing with Arrays

🏆 Top Interview Problems

1. Two Sum

2. Best Time to Buy & Sell Stock

3. Maximum Subarray

4. Move Zeroes

5. Rotate Array

6. Product of Array Except Self

7. Merge Sorted Arrays

8. Trapping Rain Water

⚠️ Edge Cases to Remember

🎨 Visualization Examples

Sliding Window (size k=3)

Two-Pointer Reversal

Kadane's Algorithm Walk-through

📝 Practice Problems

🚫 Common Mistakes & How to Avoid Them

🚀 How to Use This Repo

🤝 Contributing

📄 License

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Contributors

Uh oh!

Languages

Packages