10. Array

Introduction

---

Array basics:

• Contiguous block of memory
• Elements of same data type
• Fixed size set at creation
• Faster access than other data structures
• Stored in stack memory
• Address is read-only
• Can create variable length arrays in C++

Declaration & Allocation

---

dataType arrayName[arraySize];

Accessing Elements

---

Use index to access elements within bounds

arrayName[0]; // First element
arrayName[i]; // ith element

Initialization

---

int arr[3] = {1, 2, 3}; // Initializer list 
int arr2[3] = {}; // Default initialization

Array Creation

---

#include<iostream>
using namespace std;
 
int main(){
	// Create
	int arr[100] = {1,2,3,4};
	
	cout << arr[0] << endl;
	cout << arr[1] << endl;
	cout << arr[2] << endl;
	
	int n = sizeof(arr)/sizeof(int);
	cout << n << endl;
	
	// Print all the elements of the array 
	for(int i=0, i<=n, i++){
		cout << arr[i] << " , ";
	}
	cout << endl;
	
	return 0;
}

The key things to note:

• sizeof(arr) returns the total size in bytes of the array arr
• Each integer element occupies 4 bytes
• There are X elements in the array
• So total size = X * size of each element
• By dividing the total size by the size of 1 element, we get the number of elements, which is X

Array Input

---

To take array input from the user:

#include<iostream>
using namespace std;
 
int main(){
	
	// Take size of array
	int n;
	cin >> n;
	
	// Declare array
	int arr[n];
	
	// Take input for each element
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	
	// Print all the elements of the array 
	for(int i=0; i<n; i++){
		cout << arr[i] << " , "
	}
	cout << endl;
}

• First take size of array n
• Declare array of size n dynamically
• Run loop till n and use cin to input element by element

We can also calculate total array size using:

int size = sizeof(arr)/sizeof(int);

Passing Arrays to Functions

---

Arrays can be passed to functions in two ways:

Passing entire array

---

#include<iostream>
using namespace std;
 
 
// Array name is an address which is read only
// Pointer variable can hold the address of any bucket/array in the memory 
void print(int * myArray){
	cout << sizeof(myArray) << endl;
}
 
int main(){
	
	// Take Input N
	int n;
	cin >> n;
	
	// Create
	int arr[n];
	for(int i; i=0; i++){
		cin >> arr[i];
	}
	
	// Array capacity 
	cout << sizeof(arr)/sizeof(int) << endl;
	
	print(arr);
	
	return 0;
}
 
// When done without pointer 
// 1 warning
/*Output
5
12345
20 <- Main loop <- Size of the array 
8 <- Size of Pointer variable
*/ 

Passing pointer to first element

---

#include<iostream>
using namespace std;
 
 
// Array name is an address which is read only
// Pointer variable can hold the address of any bucket/array in the memory 
void print(int * myArray,int n){
	
	for(int i=0; i < n; i++){
		cout << myArray[i] << endl;
	}
}
 
int main(){
	
	// Take Input N
	int n;
	cin >> n;
	
	// Create
	int arr[n];
	for(int i; i=0; i++){
		cin >> arr[i];
	}
	
	// Array capacity 
	cout << sizeof(arr)/sizeof(int) << endl;
	
	print(arr, n);
	
	return 0;
}

In both cases, modifications to array in function are reflected in original array.

Time Complexity: Passing array only passes address. So it takes constant time O(1).

Linear Search

---

Linear search is used to find the position of a given element in an array.

It works by traversing the array sequentially and comparing each element to the search value.

#include<iostream>
using namespace std;
 
void print(int * myArray,int n){
	
	for(int i=0; i < n; i++){
		cout << myArray[i] << " , ";
	}
	cout << endl;
}
 
// Return index if present, otherwise -1
int linearSearch(int arr[], int n, int key) {
 
  for(int i = 0; i < n; i++) {
   
    // If key is found
    if(arr[i] == key) {  
      return i; 
    }
 
  }
 
  // If key not found 
  return -1; 
}
 
int main(){
	
	// Take Input N
	int n;
	cin >> n;
	
	// Input an array
	int arr[n];
	for(int i; i=0; i++){
		cin >> arr[i];
	}
	
	// Output an array 
	print(arr, n);
	
	// Which element to search 
	int key;
	cin >> key;
	
	int res = linearSearch(arr, n, key);
	if(res==-1){
		cout << "Element not found" << endl;
	}
	else{
		cout << "Present at index : " << endl;
	}
	return 0;
}

Implementation:

• Start from the first element
• Compare each element with search key
• If match found, return index
• If no match, return -1

Time Complexity:

• O(n) - Linear scan of entire array

Applications:

• Find if an element is present or not
• Find index/position of an element

Reversing an Array

---

Reversing an array means changing the order of elements to opposite direction.

For example, if original array is:

1, 2, 3, 4, 5

Reversed array would be:

5, 4, 3, 2, 1

There are two common methods:

Using Loop

---

void reverseArray(int arr[], int n) {
  for(int i = n-1; i >= 0; i--) {
    cout << arr[i] << " "; 
  }
}  

• Start from end of array
• Print each element in reverse

By Index Manipulation

---

void reverseArray(int arr[], int n){
  
  for(int i = 0; i < n; i++){
    cout << arr[n - i - 1] << " "; 
  } 
}

• Print $i^{th}$ element from end
• E.g. $0^{th}$ element from end is n-1

Time Complexity: O(n) to traverse array once

Reversing In-Place

---

In-place reversal modifies array within same memory.

void reverseInPlace(int arr[], int n) {
  
  int start = 0;
  int end = n-1; 
  
  while(start < end) {
    swap(arr[start], arr[end]);
    start++; 
    end--;
  }  
}

• Initialize start and end index
• In loop, swap elements from ends
• Increment start, decrement end
• Repeat till start < end

Benefits:

• Does not require extra memory
• Modifies array in-place

Subarrays

---

A subarray is a contiguous part of an array.

For an array arr[] of size n, we can form different subarrays as follows:

#include<iostream>
using namespace std;
 
int main(){
	
	// Subarray 
	int arr[] = {1, 2, 3, 4, 5}; 
	int n = sizeof(arr)/sizeof(int);
	
	// Generate all subarrays
	for(int i = 0; i < n; i++) {
	  for(int j = i; j < n; j++) {
	   
	    // Print current subarray
	    for(int k = i; k <= j; k++) {
	      cout << arr[k] << " "; 
	    }
	    cout << endl; 
	
	  }
	}
	return 0;
}

This generates subarrays starting from arr[i] to arr[j].

For example for above array, it will print:

1  
1 2 
1 2 3
1 2 3 4
1 2 3 4 5
2
2 3
2 3 4 
2 3 4 5
3
3 4
3 4 5
4 
4 5
5

So in this way, we can generate all subsequences of an array.

Applications:

• Finding maximum sum contiguous subarray (Kadane’s algorithm)
• Finding longest contiguous subarray with a given property
• Many other array/string problems

Time Complexity:

• O(N^3) to print all subarrays
• Can be optimized to O(N^2) using better loops

Multidimensional Arrays

---

• Arrays containing other arrays
• Create 2D, 3D etc arrays
• Access elements using multiple indices

2D Arrays

---

A 2D array is an array of arrays. It is a table of elements arranged in rows and columns.

For example:

1 2 3
4 5 6
7 8 9

Declaration

We declare a 2D array by specifying the number of rows and columns:

int arr[100][100]; // Declares a 2D array of size 100 x 100

Initialization

A 2D array can be initialized by nested for loops:

for(int i=0; i<rows; i++){
  for(int j=0; j<cols; j++){
    cin >> arr[i][j]; 
  }
} 

This allows us to initialize each element one by one.

Accessing Elements

To access a particular element, we use two index values - row index and column index:

arr[i][j] // ith row and jth column   

For example:

arr[2][3] = 5; // Row 3, Column 4 element

Traversal

We can traverse a 2D array using nested for loops.

To print all elements:

for(int i=0; i<rows; i++){
  for(int j=0; j<cols; j++){
	 cout << arr[i][j] << " ";
  }
  cout << endl; 
}

Applications

• Tabular data
• Matrices
• Images
• Games like chess, sudoku etc.

2D arrays allow us to represent multi-dimensional data for various applications. The elements are stored contiguously in row-major order in memory for fast access.

NOTE

Defining columns is a must .

#include<iostream>
using namespace std;
 
int main(){
	
	// 2D arrays
	int arr[100][100];
	
	// Rows, columns
	int rows;
	int cols;
	cout << "Rows: "; 
	cin >> rows; 
	cout << "Columns: "; 
	cin >> cols;
	
	// Read a 2D array 
	for(int i=0; i<rows; i++){
		for(int j=0; j<cols; j++){
			cin >> arr[i][j];
		}
		cout << endl;
	}
	
	// Print a 2D array 
	for(int i=0; i<rows; i++){
		for(int j=0; j<cols; j++){
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	
	
	return 0;
}

Memory (Row Major Order)

Even though a 2D array is conceptualized as a table of rows and columns, physically the elements are stored linearly in memory.

In row major order, the elements are stored row-wise i.e first all elements of row 1, then row 2 and so on.

For example:

1 2 3
4 5 6
7 8 9 

This is stored in memory in the following linear sequence:

1 2 3 4 5 6 7 8 9

Row major order allows easy access along rows, since each row’s elements are stored contiguously.

So if we access arr[1][2]:

• Go to 2nd row (address is calculated based on number of cols)
• Go to 3rd position within that row

This access takes constant time O(1).

However, column-wise access may be slower as the column elements are not contiguous. To fetch a column we may need to traverse through multiple rows.

Overall, the linear row-major storage allows simplicity in computing locations, since 2D logical coordinates can be mapped to 1D physical location.

Wave Print

---

Wave print refers to printing the elements of a 2D array column-wise in a wave pattern.

For example, for the following array:

1 2 3 
4 5 6  
7 8 9

Wave print would be:

1 4 7 8 5 2 3 6 9

Here is an implementation in C++:

#include<iostream>
using namespace std;
 
void wavePrint(int arr[][100], int rows, int cols){
	
	// Iterate on every column
	for(int col = 0; col < cols; col++){
		if(col%2==0){
			for(int row=0; row <= rows-1; row++){
				cout << arr[row][col] << " ";
			}
		}
		else{
			for(int row = rows-1; row >= 0; row--){
				cout << arr[row][col] << " ";
			}
		}
	}
	cout << endl;
}
 
int main(){
	
	// 2D arrays
	int arr[100][100];
	
	// Rows, columns
	int rows;
	int cols;
	cout << "Rows: "; 
	cin >> rows; 
	cout << "Columns: "; 
	cin >> cols;
	
	// Read a 2D array 
	for(int i=0; i<rows; i++){
		for(int j=0; j<cols; j++){
			cin >> arr[i][j];
		}
		cout << endl;
	}
	
	// Print a 2D array 
	for(int i=0; i<rows; i++){
		for(int j=0; j<cols; j++){
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	
	wavePrint(arr, rows, cols);
	
	return 0;
}

The key steps are:

• Iterate through each column
• Check if column is even or odd using col%2
• If even column:
  • Print from top to bottom
• If odd column:
  • Print from bottom to top

The time complexity is O(rows x cols) since we are iterating through every element once.

INFO

Wave print can be useful for problems where we need to traverse a 2D array in zig-zag fashion from top left to bottom right. It is an alternative way to traverse a 2D array.