Array Concepts with Examples
Concept: Array Basics
Description: Understanding array declaration, initialization, traversal, and updating elements.
Example Problem: Print all elements of an array
Input: arr = [1, 2, 3, 4, 5]
Output: 1 2 3 4 5
Concept: Find Max/Min Element
Description: Iterate through the array to find the largest and smallest element.
Example Problem: Find maximum element
Input: arr = [10, 4, 7, 2, 9]
Output: Max = 10
Concept: Reverse an Array
Description: Reverse array elements in-place using two-pointer approach.
Example Problem: Reverse array
Input: arr = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Concept: Binary Search
Description: Search in sorted array by dividing search space into halves.
Example Problem: Find element index
Input: arr = [1, 3, 5, 7, 9], target = 5
Output: Index = 2
Concept: Two-Pointer Technique
Description: Use two indices to solve problems like pair sum, reverse, or partition.
Example Problem: Two sum in sorted array
Input: arr = [2, 3, 4, 7, 11], target = 9
Output: [1, 3]
Concept: Sliding Window
Description: Maintain a window over array elements to find optimal values.
Example Problem: Max sum of subarray of size k
Input: arr = [1, 2, 3, 4, 5], k = 3
Output: 12
Concept: Prefix Sum
Description: Precompute cumulative sums for fast range queries.
Example Problem: Range sum query
Input: arr = [1, 2, 3, 4, 5], range = (1, 3)
Output: 9
Concept: Kadane's Algorithm
Description: Find maximum subarray sum in O(n).
Example Problem: Max sum subarray
Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Concept: Matrix Operations
Description: Work with 2D arrays for rotation, transpose, and traversal.
Example Problem: Transpose matrix
Input: [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Concept: Monotonic Stack
Description: Stack-based approach to solve Next Greater Element or Largest Rectangle problems.
Example Problem: Next Greater Element
Input: arr = [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]
