Module 12: Arrays (Data Structures)

Learning Objectives

By the end of this module, you will be able to:

• Understand arrays as a fundamental data structure.
• Perform traversal, insertion, deletion, searching, updating, and rotation operations.
• Learn Prefix Sum and Sliding Window techniques.
• Implement Linear Search, Binary Search, and Kadane's Algorithm.
• Analyze the time complexity of array operations.
• Solve common array interview problems.

Introduction

Arrays are the first and most important data structure in computer science.

Many advanced data structures are built using arrays, including:

• Stacks
• Queues
• Heaps
• Hash Tables
• Dynamic Arrays
• Matrices

Most coding interviews begin with array-based problems because arrays teach important concepts such as indexing, searching, traversal, and optimization.

What is an Array?

An array is a linear data structure that stores elements of the same data type in contiguous memory locations.

Example:

textCopy
1Index : 0   1   2   3   4
2Value : 12  25  18  40  30

Characteristics:

• Fixed size
• Contiguous memory allocation
• Fast random access using indexes
• Stores homogeneous data

Time Complexity of Array Operations

• Assuming free space is available at the end.

Array Traversal

Traversal means visiting every element exactly once.

Example

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[] = {10,20,30,40,50};
6    int size = sizeof(arr)/sizeof(arr[0]);
7
8    for(int i=0;i<size;i++)
9    {
10        printf("%d ", arr[i]);
11    }
12
13    return 0;
14}

Output

textCopy
110 20 30 40 50

Time Complexity

textCopy
1O(n)

Insertion in an Array

To insert an element at a specific position:

1. Shift elements to the right.
2. Insert the new element.

Example

textCopy
1Before
2
310 20 30 40
4
5Insert 25 at index 2
6
7After
8
910 20 25 30 40

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[10] = {10,20,30,40};
6    int size = 4;
7    int position = 2;
8    int value = 25;
9
10    for(int i=size; i>position; i--)
11    {
12        arr[i] = arr[i-1];
13    }
14
15    arr[position] = value;
16    size++;
17
18    for(int i=0;i<size;i++)
19        printf("%d ", arr[i]);
20
21    return 0;
22}

Time Complexity

textCopy
1O(n)

Deletion from an Array

Delete an element by shifting remaining elements to the left.

Example

textCopy
1Before
2
310 20 30 40 50
4
5Delete 30
6
7After
8
910 20 40 50

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[] = {10,20,30,40,50};
6    int size = 5;
7    int position = 2;
8
9    for(int i=position;i<size-1;i++)
10    {
11        arr[i] = arr[i+1];
12    }
13
14    size--;
15
16    for(int i=0;i<size;i++)
17        printf("%d ", arr[i]);
18
19    return 0;
20}

Time Complexity

textCopy
1O(n)

Searching

Searching means finding the position of an element.

Two common searching algorithms:

• Linear Search
• Binary Search

Updating an Element

Updating replaces an existing value.

Example

textCopy
1Before
2
310 20 30
4
5Update index 1
6
7After
8
910 99 30

cCopy
1arr[1] = 99;

Time Complexity

textCopy
1O(1)

Array Rotation

Rotate an array to the right by one position.

Before

textCopy
11 2 3 4 5

After

textCopy
15 1 2 3 4

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[] = {1,2,3,4,5};
6    int size = 5;
7
8    int last = arr[size-1];
9
10    for(int i=size-1;i>0;i--)
11    {
12        arr[i]=arr[i-1];
13    }
14
15    arr[0]=last;
16
17    for(int i=0;i<size;i++)
18        printf("%d ",arr[i]);
19
20    return 0;
21}

Time Complexity

textCopy
1O(n)

Prefix Sum

Prefix Sum stores cumulative sums, enabling fast range-sum queries.

Example Array

textCopy
12 4 6 8

Prefix Sum

textCopy
12 6 12 20

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={2,4,6,8};
6    int size=4;
7
8    int prefix[4];
9
10    prefix[0]=arr[0];
11
12    for(int i=1;i<size;i++)
13    {
14        prefix[i]=prefix[i-1]+arr[i];
15    }
16
17    for(int i=0;i<size;i++)
18        printf("%d ",prefix[i]);
19
20    return 0;
21}

Time Complexity

textCopy
1O(n)

Applications

• Range sum queries
• Competitive programming
• Data analysis

Sliding Window Technique

Used for problems involving contiguous subarrays.

Example

Find the maximum sum of a subarray of size k.

Instead of recalculating every window, subtract the outgoing element and add the incoming element.

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={2,1,5,1,3,2};
6    int k=3;
7    int size=6;
8
9    int windowSum=0;
10
11    for(int i=0;i<k;i++)
12        windowSum+=arr[i];
13
14    int maxSum=windowSum;
15
16    for(int i=k;i<size;i++)
17    {
18        windowSum+=arr[i]-arr[i-k];
19
20        if(windowSum>maxSum)
21            maxSum=windowSum;
22    }
23
24    printf("Maximum Sum = %d",maxSum);
25
26    return 0;
27}

Output

textCopy
1Maximum Sum = 9

Time Complexity

textCopy
1O(n)

Linear Search

Linear Search checks each element one by one.

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={12,25,18,40,30};
6    int size=5;
7    int key=40;
8
9    for(int i=0;i<size;i++)
10    {
11        if(arr[i]==key)
12        {
13            printf("Found at index %d",i);
14            return 0;
15        }
16    }
17
18    printf("Not Found");
19
20    return 0;
21}

Time Complexity

textCopy
1Best Case  : O(1)
2Average    : O(n)
3Worst Case : O(n)

Binary Search

Binary Search works only on sorted arrays.

Algorithm

1. Find the middle element.
2. Compare with target.
3. Search the left or right half.
4. Repeat until found.

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={5,10,15,20,25,30,35};
6    int size=7;
7    int target=25;
8
9    int left=0;
10    int right=size-1;
11
12    while(left<=right)
13    {
14        int mid=left+(right-left)/2;
15
16        if(arr[mid]==target)
17        {
18            printf("Found at index %d",mid);
19            return 0;
20        }
21
22        if(target<arr[mid])
23            right=mid-1;
24        else
25            left=mid+1;
26    }
27
28    printf("Not Found");
29
30    return 0;
31}

Time Complexity

textCopy
1O(log n)

Kadane's Algorithm

Kadane's Algorithm finds the maximum sum subarray in linear time.

Example

textCopy
1Array
2
3-2 1 -3 4 -1 2 1 -5 4
4
5Maximum Sum
6
76
8
9Subarray
10
114 -1 2 1

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={-2,1,-3,4,-1,2,1,-5,4};
6    int size=9;
7
8    int maxCurrent=arr[0];
9    int maxGlobal=arr[0];
10
11    for(int i=1;i<size;i++)
12    {
13        if(maxCurrent+arr[i]>arr[i])
14            maxCurrent=maxCurrent+arr[i];
15        else
16            maxCurrent=arr[i];
17
18        if(maxCurrent>maxGlobal)
19            maxGlobal=maxCurrent;
20    }
21
22    printf("Maximum Sum = %d",maxGlobal);
23
24    return 0;
25}

Output

textCopy
1Maximum Sum = 6

Time Complexity

textCopy
1O(n)

Practice Project 1: Largest Element

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={10,25,15,60,45};
6    int largest=arr[0];
7
8    for(int i=1;i<5;i++)
9    {
10        if(arr[i]>largest)
11            largest=arr[i];
12    }
13
14    printf("Largest = %d",largest);
15
16    return 0;
17}

Practice Project 2: Second Largest Element

cCopy
1#include <stdio.h>
2#include <limits.h>
3
4int main()
5{
6    int arr[]={10,40,20,80,60};
7
8    int largest=INT_MIN;
9    int second=INT_MIN;
10
11    for(int i=0;i<5;i++)
12    {
13        if(arr[i]>largest)
14        {
15            second=largest;
16            largest=arr[i];
17        }
18        else if(arr[i]>second && arr[i]!=largest)
19        {
20            second=arr[i];
21        }
22    }
23
24    printf("Second Largest = %d",second);
25
26    return 0;
27}

Practice Project 3: Missing Number

Given numbers from 1 to n with one number missing.

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={1,2,3,5};
6    int n=5;
7
8    int expected=n*(n+1)/2;
9    int actual=0;
10
11    for(int i=0;i<n-1;i++)
12        actual+=arr[i];
13
14    printf("Missing Number = %d",expected-actual);
15
16    return 0;
17}

Time Complexity

textCopy
1O(n)

Practice Project 4: Rotate Array by One Position

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[]={1,2,3,4,5};
6    int size=5;
7
8    int first=arr[0];
9
10    for(int i=0;i<size-1;i++)
11        arr[i]=arr[i+1];
12
13    arr[size-1]=first;
14
15    for(int i=0;i<size;i++)
16        printf("%d ",arr[i]);
17
18    return 0;
19}

Output

textCopy
12 3 4 5 1

Common Mistakes to Avoid

• Accessing array indexes outside valid bounds.
• Using Binary Search on an unsorted array.
• Forgetting to update the array size after insertion or deletion.
• Confusing left and right rotations.
• Recomputing subarray sums instead of using the Sliding Window technique.
• Forgetting to initialize variables in algorithms like Kadane's Algorithm.

Best Practices

• Validate array indexes before accessing elements.
• Use meaningful variable names such as numbers, marks, or prices.
• Prefer Binary Search over Linear Search when the array is sorted.
• Use Prefix Sum for multiple range-sum queries.
• Apply the Sliding Window technique for contiguous subarray problems.
• Use Kadane's Algorithm to find the maximum subarray sum efficiently.
• Always analyze the time and space complexity of your solution before optimizing.

Module Summary

In this module, you learned:

• How arrays work as a linear data structure.
• Array operations such as traversal, insertion, deletion, searching, updating, and rotation.
• The Prefix Sum technique for efficient range queries.
• The Sliding Window technique for optimizing subarray problems.
• Searching algorithms including Linear Search and Binary Search.
• Kadane's Algorithm for finding the maximum sum subarray.
• How to solve common interview problems such as finding the largest element, second largest element, missing number, and rotating an array.

After completing this module, you'll be ready to learn Linked Lists, where you'll study singly, doubly, and circular linked lists, dynamic memory allocation, pointer manipulation, and efficient insertion and deletion operations.