Mastering Arrays in Data Structures and Algorithms: From Basics to Advanced
1. Introduction to Arrays
An array is a data structure used to store multiple values in a single variable, instead of declaring separate variables for
each value.
Arrays store elements in contiguous memory locations and are accessed using an index. The first element has index 0.
Types of Arrays:
- One-dimensional (1D): int[] arr = {1, 2, 3};
- Two-dimensional (2D): int[][] matrix = {{1,2},{3,4}};
- Multi-dimensional: Arrays with more than 2 dimensions
In memory, elements are stored sequentially. Accessing any element has a time complexity of O(1).
2. Basic Array Operations
- Insertion: Add element at a specific index (may require shifting elements)
- Deletion: Remove element at a specific index
- Traversal: Visiting each element once (for loop)
- Searching:
- Linear Search: O(n)
- Binary Search (sorted array): O(log n)
- Updating: Changing the value at a specific index
Example (Python - Traversal):
arr = [10, 20, 30]
for i in arr:
print(i)
3. Array Interview Questions (Easy)
1. Find Max Element:
arr = [1, 4, 2, 9]
Mastering Arrays in Data Structures and Algorithms: From Basics to Advanced
print(max(arr)) # 9
2. Reverse an Array:
arr[::-1]
3. Check if Sorted:
def is_sorted(arr):
return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
4. Merge Two Sorted Arrays:
Use two-pointer approach to merge in O(n+m) time.
4. Intermediate Level Problems
1. Kadane's Algorithm:
def maxSubArray(arr):
max_sum = current = arr[0]
for num in arr[1:]:
current = max(num, current + num)
max_sum = max(max_sum, current)
return max_sum
2. Move Zeros:
def move_zeros(arr):
non_zeros = [x for x in arr if x != 0]
return non_zeros + [0]*(len(arr)-len(non_zeros))
3. Remove Duplicates (Sorted):
def remove_duplicates(arr):
return list([Link](arr))
Mastering Arrays in Data Structures and Algorithms: From Basics to Advanced
5. Advanced Concepts
1. Prefix Sum:
Given an array, compute sum[i] = sum[i-1] + arr[i]
2. Sliding Window:
For problems involving subarrays of size k (e.g., max sum of k elements)
3. Binary Search on Answer:
Used when searching in answer space (e.g., minimum largest sum)
4. Bit Manipulation:
XOR of all elements to find unique one: result = a ^ b ^ c ^ a ^ b -> result = c
6. Real-World Applications
- Image Processing: Pixels stored in 2D arrays
- Game Boards: Chess, Sudoku can be modeled using arrays
- Spreadsheet software internally uses 2D arrays
- NumPy in Python performs advanced data operations using arrays
- OS uses arrays for memory blocks
7. Best Practices
- Avoid index out-of-bound errors
- Prefer arrays for fixed size datasets
- Use descriptive variable names (e.g., studentMarks)
- Know array vs dynamic alternatives (ArrayList, LinkedList)
- Free memory if using low-level language like C++
8. Code Snippets
Java Example - Reverse Array:
Mastering Arrays in Data Structures and Algorithms: From Basics to Advanced
public class ReverseArray {
public static void reverse(int[] arr) {
int left = 0, right = [Link] - 1;
while(left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; right--;
Python Example - Find Max:
arr = [5, 3, 7]
print(max(arr))
9. Summary and Cheat Sheet
| Operation | Time Complexity |
|------------------|------------------|
| Access | O(1) |
| Search (Linear) | O(n) |
| Search (Binary) | O(log n) |
| Insertion | O(n) |
| Deletion | O(n) |
Techniques:
- Two-pointer: Sorted arrays, pairing problems
- Sliding Window: Subarray sums, fixed-size windows
10. References
Mastering Arrays in Data Structures and Algorithms: From Basics to Advanced
- [Link]
- [Link]
- [Link]
- [Link]