Arrays

---

TOPIC NAME: Arrays

1. ABOUT THE TOPIC

• Arrays store elements in contiguous memory and are usually the first data structure you learn in DSA.
• This topic is important because arrays appear everywhere: searching, sorting, hashing, prefix sums, greedy, DP, and sliding window problems all start here.
• In interviews, arrays are used to test indexing control, observation skills, optimization ability, and knowledge of reusable patterns.

2. KEY CONCEPTS

• Prefix Sum: Precompute cumulative sums to answer range queries quickly.
• Two Pointers: Move two indices smartly to reduce nested loops.
• Sliding Window: Maintain a valid subarray while expanding and shrinking the range.
• Kadane’s Algorithm: Tracks the best subarray sum in linear time.
• In-place Rearrangement: Modify the array without extra memory when the problem allows.
• Difference Between Sorted and Unsorted Arrays: Sorted arrays unlock binary search and pointer-based optimizations.

3. COMMON PATTERNS

• Two Pointer: Use when the answer depends on pairs, partitioning, or opposite ends of an array.
• Sliding Window: Use for subarray or substring questions involving a continuous range.
• Kadane’s Algorithm: Use when asked for maximum sum over a contiguous subarray.
• Prefix Sum: Use when repeated sum checks are needed.
• Hash Map + Array: Use when you need fast complement lookup or frequency tracking.

4. COMPLEXITY GUIDE

• Brute force on arrays is often O(n^2) because it checks every pair or every subarray.
• The most common optimized targets are O(n) with hashing/pointers or O(n log n) with sorting.
• Extra space is often a tradeoff for speed, especially with hash maps and prefix storage.
• In-place array changes reduce space to O(1) but often demand careful ordering.

5. QUESTIONS (WITH LINKS)

EASY:

• Two Sum
  Link: https://leetcode.com/problems/two-sum/

• Move Zeroes
  Link: https://leetcode.com/problems/move-zeroes/

• Missing Number
  Link: https://leetcode.com/problems/missing-number/

MEDIUM:

• Maximum Subarray
  Link: https://leetcode.com/problems/maximum-subarray/

• Next Permutation
  Link: https://leetcode.com/problems/next-permutation/

• Set Matrix Zeroes
  Link: https://leetcode.com/problems/set-matrix-zeroes/

• Sort Colors
  Link: https://leetcode.com/problems/sort-colors/

• Rearrange Array Elements by Sign
  Link: https://leetcode.com/problems/rearrange-array-elements-by-sign/

HARD:

• Merge Intervals
  Link: https://leetcode.com/problems/merge-intervals/

• Trapping Rain Water
  Link: https://leetcode.com/problems/trapping-rain-water/

6. INTERVIEW TIPS

• Watch for off-by-one errors when shrinking windows or swapping indices.
• Clarify whether order must be preserved before choosing an in-place technique.
• For interval questions, sort first unless the problem explicitly guarantees order.
• For matrix problems, decide whether using first row or column as markers is safe.

7. PRACTICE STRATEGY

• Start with easy indexing and hashing problems.
• Then practice two pointers, sliding window, prefix sum, and Kadane separately.
• End with interval and matrix transformation problems because they mix multiple ideas.

8. BLOG SEO META

• Title: Arrays in DSA | Patterns, Interview Tricks, and LeetCode Practice
• Description: Learn arrays for coding interviews with two pointers, sliding window, prefix sums, Kadane’s algorithm, and curated LeetCode questions.
• Keywords: arrays DSA, two pointers, sliding window, Kadane algorithm, array interview questions