PROBLEM SOLVING - ARRAYS INTRODUCTION

Array Basics in C

Array Definition

An array is a collection of items stored at contiguous memory locations. In C, arrays are:

  • Fixed-size - Size must be known at compile time
  • Homogeneous - All elements are of the same type
  • Zero-indexed - First element is at index 0
// Syntax:
data_type array_name[array_size];

Array Applications

Arrays are fundamental data structures used in various applications:

  • Storing and accessing sequential data
  • Implementing other data structures (stacks, queues, heaps)
  • Matrix operations
  • Sorting and searching algorithms
  • Lookup tables and hash tables
  • CPU scheduling
  • Image processing

Array Initialization

Arrays can be initialized in several ways in C:

// Method 1: Initialize with values
int arr1[5] = {1, 2, 3, 4, 5};

// Method 2: Initialize with partial values (rest set to 0)
int arr2[5] = {1, 2}; // [1, 2, 0, 0, 0]

// Method 3: Initialize without size (compiler determines size)
int arr3[] = {1, 2, 3, 4, 5};

// Method 4: Initialize with zeros
int arr4[5] = {0}; // All elements 0

Array Types

C supports different types of arrays:

  • 1D Arrays: Simple linear arrays
  • 2D Arrays: Arrays of arrays (matrices)
  • Multi-dimensional Arrays: Arrays with more than two dimensions
  • Variable Length Arrays (VLA): Size determined at runtime (C99+)

Accessing 1D Arrays

Elements in a 1D array are accessed using their index:

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

// Accessing elements
int first = numbers[0]; // 10
int third = numbers[2]; // 30

// Modifying elements
numbers[1] = 25; // Changes second element to 25

// Looping through array
for(int i = 0; i < 5; i++) {
    printf("%d ", numbers[i]);
}

Accessing 2D Arrays

2D arrays (matrices) are accessed using two indices:

// Declaration and initialization
int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// Accessing elements
int topLeft = matrix[0][0]; // 1
int center = matrix[1][1];  // 5

// Modifying elements
matrix[2][1] = 10; // Changes bottom-center to 10

// Nested loop for traversal
for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
        printf("%d ", matrix[i][j]);
    }
    printf("\n");
}

PROBLEM SOLVING - ARRAYS TRICKS

1-Dimensional Arrays Approaches

# Technique Use Case Approach Complexity Examples
1 Two-Pointer Process pairs, remove duplicates, or find subarrays Use two pointers (start & end, or slow & fast) to traverse efficiently O(n)
  • Reverse an array
  • Search an element
  • Remove duplicates
  • Two-sum problem
2 Sliding Window Subarrays with fixed size or condition Maintain a window (subarray) and adjust size dynamically O(n)
  • Max sum of k consecutive
  • Longest subarray ≤ K
  • Min size subarray ≥ target
3 Binary Search Sorted array with O(log n) search Divide search space in half repeatedly O(log n)
  • Find in sorted array
  • First/last occurrence
  • Peak in mountain array
  • Rotated sorted array
4 Cyclic Rotations Rotating array or reversing parts Use reversal tricks in O(1) space O(1) space
  • Rotate array right by k
  • Reverse portions
  • Circular buffer ops
5 Frequency Counting Count occurrences or find duplicates Use hash map or array for frequencies O(n) time
  • Find duplicates
  • First non-repeating
  • Disappeared numbers
  • Group anagrams
6 Swap & Reorder Modify array in-place Track correct position and swap elements In-place
  • Move zeros to end
  • Segregate even-odd
  • Dutch flag problem
  • Move negatives
7 Prefix Sum Compute range sums efficiently Precompute sums for O(1) range queries O(n) prep O(1) query
  • Equilibrium index
  • Subarray sum = K
  • Range sum queries
  • Max average subarray
8 Kadane's Algorithm Maximum sum of contiguous subarray Track current sum, reset if negative O(n) time O(1) space
  • Max subarray sum
  • Max product subarray
  • Circular subarray sum
  • Max sum with k elements

Common Array Operations

Finding Min & Max in One Pass 
int min = arr[0], max = arr[0];
for(int i = 1; i < n; i++) {
    if(arr[i] < min) min = arr[i];
    if(arr[i] > max) max = arr[i];
}
printf("Min: %d, Max: %d", min, max);
Time Complexity: O(n)
Moving Zeros to End (In-Place) 
int nonZero = 0;
for(int i = 0; i < n; i++) {
    if(arr[i] != 0) {
        arr[nonZero++] = arr[i];
    }
}
while(nonZero < n) arr[nonZero++] = 0;
Time Complexity: O(n)
Swapping Without Temp Variable 
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
Note: Potential overflow risk
Reverse an Array In-Place 
int i = 0, j = n - 1;
while(i < j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    i++; j--;
}
Time Complexity: O(n)
Check for Duplicate Elements 
for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        if(arr[i] == arr[j])
            printf("Duplicate: %d\n", arr[i]);

For better performance, use hash or sort + adjacent check.

Time Complexity: O(n²)
Frequency Count of Elements 
for (int i = 0; i < n; i++) {
    int count = 1;
    if (arr[i] == -1) continue;
    for (int j = i + 1; j < n; j++) {
        if (arr[i] == arr[j]) {
            count++;
            arr[j] = -1; // mark as visited
        }
    }
    printf("%d appears %d times\n", arr[i], count);
}
Time Complexity: O(n²)

2D Array Problem-Solving Tricks

# Trick Description Use Case
1 Row-wise & Column-wise Traversal Use nested loops: for(i) outer for rows, for(j) inner for columns Printing, summing, input
2 Diagonal Traversal For main diagonal: i == j, for secondary: i + j == n – 1 Pattern, symmetry
3 Transpose Matrix Swap elements: mat[i][j] = mat[j][i] Rotation, matrix algebra
4 Matrix Rotation Rotate 90° clockwise: Transpose + reverse each row Games, image rotation
5 Search in Sorted 2D Matrix Start from top-right, go left/down accordingly Matrix binary search
6 Spiral Traversal Use 4 bounds: top, bottom, left, right and loop inward Spiral print
7 Boundary Traversal Print only outermost elements Shell printing
8 Count Zeros or Ones Efficiently If sorted, use binary search per row Optimized counting
9 Sum of Each Row/Col Use accumulator per loop Reports, histogram
10 Prefix Sum Matrix (2D) prefix[i][j] = above + left - diagonal + current Submatrix sum queries
11 In-place Element Swap Use a temp variable or arithmetic swaps Memory-efficient update
12 Max Submatrix Sum (Kadane 2D) Apply Kadane's algorithm on columns over rows Advanced DP
13 Flip Image (Horizontal/Vertical) Reverse rows or columns Pattern problems
14 Flood Fill / DFS on Grid Use recursion on grid[i][j] and valid neighbors Maze, islands
15 Pattern Matching in Matrix Search a small matrix pattern in large one 2D pattern search
Related Array Resources
Basic Programs
Interview Questions
MCQs
Arrays Tricks