Arrays for Competitive Programming
In this article, we will be discussing Arrays which is one of the most commonly used data structure. It also plays a major part in Competitive Programming. Moreover, we will see built-in methods used to write short codes for array operations that can save some crucial time during contests.
Table of Content
- What are Arrays in Programming?
- Significance of Arrays in Competitive Programming (CP)
- How to implement Arrays in different Programming Languages?
- Array Hacks for Competitive Programming (CP)
- Array Concepts for Competitive Programming (CP)
What are Arrays in Programming?
An array is a collection of items of the same variable type that are stored at contiguous memory locations. It’s one of the most popular and simple data structures and is often used to implement other data structures. Each item in an array is indexed starting with 0.
Significance of Arrays in Competitive Programming (CP):
In CP, we require the solutions to be fast, array is one such data structure which provide O(1) access of data elements and it can provide various operations to be formed in O(log N) or O(N) traversals.
Significance of Arrays in comparison to other similar data structures:
Characteristics | Arrays | Linked Lists | Stacks | Queues | Hash Tables |
---|---|---|---|---|---|
Access Time | Constant time (O(1)) | Linear time (O(n)) | Constant time (O(1)) | Constant time (O(1)) | Average O(1), Worst O(n) |
Memory Allocation | Contiguous | Non-contiguous | – | – | – |
Size Flexibility | Fixed size or dynamic with resizing | Dynamic | Dynamic | Dynamic | Dynamic |
Insertion/Deletion Efficiency | Linear time (O(n)) for resizing | Constant time (O(1)) for specific location, Linear time (O(n)) for general | Constant time (O(1)) | Constant time (O(1)) | Average O(1), Worst O(n) |
Order of Elements | Maintains order | No inherent order | LIFO (Last-In-First-Out) | FIFO (First-In-First-Out) | – |
Common Applications | General-purpose data storage and manipulation | Symbol tables, memory allocation | Managing function calls, recursion | Task scheduling, breadth-first search | Databases, caching, symbol tables |
How to implement Arrays in different Programming Languages?
Since the arrays are static data structures which results in a limited usage therefore various languages provide dynamic arrays such as:
Language | Static Implementation of Arrays | Dynamic Implementation of Arrays |
---|---|---|
C | Pointer Arrays | Array implementations through Dynamic Memory Allocations |
C++ | Pointer Arrays | Vectors |
Java | Array Object of Wrapper Classes | ArrayList |
Python |
– | List |
C# | Pointer Array | List |
JavaScript |
– | List |
Array Hacks for Competitive Programming (CP):
1. Creating (Declaration) of Array in 1-Line:
vector<int> arr(n);
List<Integer> list = new ArrayList<>();
Collections.fill(list, 4);
size=10
my_list = [4] * size
let arr = new Array(n);
Time Complexity: O(N)
2. Creating (Declaration & Initialization) of Array with some Value X in 1-Line:
vector<int> arr(n, X);
List<Integer> list = new ArrayList<Integer>();
Collections.fill(list, 4);
size=10
my_list = [4] * size
const n = 5; // Example array size
const X = 10; // Example value to fill
const arr = Array.from({ length: n }, () => X);
Time Complexity: O(N)
3. Input, Access, and Output elements in Array in O(1) time
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n; // Read the size of the array
vector<int> array(n); // Declare a vector to store integers
// Taking input in the vector
for (int i = 0; i < n; i++) {
cin >> array[i];
}
// Accessing the i'th element of the vector
int i = 5;
if (i >= 0 && i < n) {
int x = array[i];
cout << "The element at index " << i << " is: " << x << std::endl;
} else {
cout << "Index out of bounds." << std::endl;
}
return 0;
}
import java.util.Scanner;
import java.util.ArrayList;
import java.util.NoSuchElementException; // Add this line
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Declare an ArrayList to store integers
ArrayList<Integer> array = new ArrayList<>();
try {
int n = scanner.nextInt(); // Read the size of the array
// Taking input in the ArrayList
for (int i = 0; i < n; i++) {
int element = scanner.nextInt();
array.add(element);
}
// Accessing the i'th element of the ArrayList
int i = 5;
if (i >= 0 && i < array.size()) {
int x = array.get(i);
System.out.println("The element at index " + i + " is: " + x);
} else {
System.out.println("Index out of bounds.");
}
} catch (NoSuchElementException e) {
System.out.println("Input not provided or input format mismatch.");
}
}
}
n = int(input()) # Read the size of the array
# Taking input in the list
array = [int(input()) for _ in range(n)]
# Accessing the i'th element of the list
i = 5
if 0 <= i < len(array):
x = array[i]
print(f"The element at index {i} is: {x}")
else:
print("Index out of bounds.")
using System;
class Program
{
static void Main()
{
// Read the size of the array
int n = Convert.ToInt32(Console.ReadLine());
// Declare a list to store integers
var array = new System.Collections.Generic.List<int>();
// Taking input in the list
for (int j = 0; j < n; j++)
{
array.Add(Convert.ToInt32(Console.ReadLine()));
}
// Accessing the i'th element of the list
int i = 5;
if (i >= 0 && i < array.Count)
{
int x = array[i];
Console.WriteLine($"The element at index {i} is: {x}");
}
else
{
Console.WriteLine("Index out of bounds.");
}
}
}
//This code is contributed by Aman.
// Read the size of the array
let n = prompt('Enter the size of the array: ');
let array = []; // Declare an array to store integers
// Function to handle recursive reading of array elements
function readArrayElements(i, n) {
if(i == n) {
// Accessing the i'th element of the array
let i = 5;
if (i >= 0 && i < n) {
let x = array[i];
console.log("The element at index " + i + " is: " + x);
} else {
console.log("Index out of bounds.");
}
} else {
let element = prompt('Enter element ' + (i+1) + ': ');
array[i] = parseInt(element); // Add element to array
readArrayElements(i+1, n); // Recursive call for next element
}
}
// Start reading array elements
readArrayElements(0, n);
Output
Index out of bounds.
Time Complexity: O(1)
4. Finding (Printing) Size or Length of the Array:
vector<int> array;
// variable s stores the size of the array
int s = array.size();
ArrayList<Integer> array = new ArrayList();
int s = array.size();
# Declare a list to store integers
array = []
# Variable s stores the size of the list
s = len(array)
print("The size of the list is:", s)
// Declare an array to store integers
let array = [];
// Variable s stores the size of the array
let s = array.length;
console.log("The size of the array is:", s);
Time Complexity: O(1)
5. Clear/Empty Array Elements in one line:
vector_name.clear()
arrayListName.clear();
array_name = []
vector_name.length = 0;
Time Complexity: O(N)
6. Inserting and Deleting element at the end of the array:
#include<bits/stdc++.h>
int main()
{
std::vector<int> vec;
vec.push_back(5); // Inserts 5 at the end
vec.push_back(10); // Inserts 10 at the end
vec.pop_back(); // Removes the last element (10)
// Print the last element of the vector
std::cout << vec.back() << std::endl;
return 0;
}
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(5); // Inserts 5 at the end
list.add(10); // Inserts 10 at the end
// Remove the last element (10)
if (!list.isEmpty()) {
list.remove(list.size() - 1);
}
// Print the last element of the ArrayList
System.out.println( list.get(list.size() - 1));
}
}
# Create an empty list
vec = []
# Inserts 5 at the end
vec.append(5)
# Inserts 10 at the end
vec.append(10)
# Removes the last element (10)
vec.pop()
# Print the list
print(vec)
let vec = [];
vec.push(5); // Inserts 5 at the end
vec.push(10); // Inserts 10 at the end
vec.pop(); // Removes the last element (10)
// Print the array after popping
console.log(vec); // Output: [5]
Time Complexity: O(1)
7. Swapping Elements in array in one line:
#include<bits/stdc++.h>
#include<algorithms>
using namespace std;
int main(){
int a=5;
int b=6;
swap(a,b);
}
import java.util.*;
public class Main {
public static void main(String[] args) {
int a = 5;
int b = 6;
int temp = a;
a = b;
b = temp;
}
}
a = 5
b = 6
a, b = b, a
let a = 5;
let b = 6;
[a, b] = [b, a];
Time Complexity: O(1)
8. Finding minimum and maximum element of the array:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> arr = {4, 2, 3, 5, 8};
int min = *min_element(arr.begin(), arr.end());
int max = *max_element(arr.begin(), arr.end());
// Do something with min and max
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> arr = new ArrayList<>();
arr.add(4);
arr.add(2);
arr.add(3);
arr.add(5);
arr.add(8);
int min = Collections.min(arr);
int max = Collections.max(arr);
}
}
arr = [4, 2, 3, 5, 8]
minimum = min(arr)
maximum = max(arr)
function main() {
const arr = [4, 2, 3, 5, 8];
const min = Math.min(...arr);
const max = Math.max(...arr);
console.log("Minimum:", min);
console.log("Maximum:", max);
}
main();
Time Complexity: O(1)
Array Concepts for Competitive Programming (CP):
2-Dimensional arrays
We define a 2 dimentional arrays as table like structure with n number of rows and m number of columns. We can access them using notation Array_name[row_number][column_number].
#include <iostream>
#include <vector>
using namespace std;
int main() {
// declaring two dimensional array
int n, m; // assuming n and m are defined elsewhere
cin >> n >> m; // assuming n and m are the dimensions of the array
vector<vector<int>> Two_D_array(n, vector<int>(m));
// taking input in the array
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> Two_D_array[i][j];
}
}
}
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // Number of rows
int m = scanner.nextInt(); // Number of columns
ArrayList<ArrayList<Integer>> TwoDArrayList = new ArrayList<>();
// Initialize the ArrayList
for (int i = 0; i < n; i++) {
TwoDArrayList.add(new ArrayList<>());
}
// Taking input in the ArrayList
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int value = scanner.nextInt();
TwoDArrayList.get(i).add(value);
}
}
}
}
n = int(input("Enter the number of rows: "))
m = int(input("Enter the number of columns: "))
TwoDList = []
# Initialize the list of lists
for i in range(n):
TwoDList.append([])
# Taking input in the list of lists
for i in range(n):
for j in range(m):
value = int(input("Enter value for position ({}, {}): ".format(i, j)))
TwoDList[i].append(value)
let n = prompt("Enter the number of rows: ");
let m = prompt("Enter the number of columns: ");
let TwoDList = [];
// Initialize the list of lists
for (let i = 0; i < n; i++) {
TwoDList.push([]);
}
// Taking input in the list of lists
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
let value = prompt(`Enter value for position (${i}, ${j}): `);
TwoDList[i].push(parseInt(value));
}
}
Sparse Array:
A sparse array or sparse matrix is an array in which most of the elements are zero. A sparse array is a data structure that efficiently represents and stores arrays where the majority of elements have the same default value. Instead of explicitly storing every element, a sparse array only records the non-default values along with their corresponding indices, reducing storage space and improving computational efficiency.
// Implementation of array representation
// of the sparse array
#include <iostream>
using namespace std;
int main()
{
int sparse[4][4] = { { 0, 0, 7, 0 },
{ 1, 0, 0, 0 },
{ 2, 0, 5, 0 },
{ 0, 8, 0, 4 } };
int s = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (sparse[i][j] != 0)
s++;
int representsparse[3][s];
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (sparse[i][j] != 0) {
representsparse[0][k] = i;
representsparse[1][k] = j;
representsparse[2][k] = sparse[i][j];
k++;
}
cout << "Representation of Sparse array using arrays : "
"\n";
for (int i = 0; i < 3; i++) {
if(i == 0)
cout << "row: ";
else if(i == 1)
cout << "column: ";
else
cout << "value: ";
for (int j = 0; j < s; j++)
cout << " " << representsparse[i][j];
cout << "\n";
}
return 0;
}
public class SparseArrayRepresentation {
public static void main(String[] args) {
// Original sparse array
int[][] sparse = {
{0, 0, 7, 0},
{1, 0, 0, 0},
{2, 0, 5, 0},
{0, 8, 0, 4}
};
// Count the non-zero elements in the sparse array
int s = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (sparse[i][j] != 0)
s++;
// Create a new array to represent the sparse array
int[][] representsparse = new int[3][s];
int k = 0;
// Fill the representsparse array with row, column, and value of non-zero elements
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (sparse[i][j] != 0) {
representsparse[0][k] = i;
representsparse[1][k] = j;
representsparse[2][k] = sparse[i][j];
k++;
}
// Display the representation of the sparse array
System.out.println("Representation of Sparse array using arrays : ");
for (int i = 0; i < 3; i++) {
if (i == 0)
System.out.print("row: ");
else if (i == 1)
System.out.print("column: ");
else
System.out.print("value: ");
for (int j = 0; j < s; j++)
System.out.print(" " + representsparse[i][j]);
System.out.println();
}
}
}
# Implementation of array representation
# of the sparse array
# Define the sparse array
sparse = [
[0, 0, 7, 0],
[1, 0, 0, 0],
[2, 0, 5, 0],
[0, 8, 0, 4]
]
# Initialize a variable to count non-zero elements
s = 0
for i in range(4):
for j in range(4):
if sparse[i][j] != 0:
s += 1
# Create a 2D array to represent the sparse array
representsparse = [[0] * s for _ in range(3)]
# Populate the representation array
k = 0
for i in range(4):
for j in range(4):
if sparse[i][j] != 0:
representsparse[0][k] = i
representsparse[1][k] = j
representsparse[2][k] = sparse[i][j]
k += 1
# Display the representation of the sparse array
print("Representation of Sparse array using arrays:\n")
for i in range(3):
if i == 0:
print("row: ", end="")
elif i == 1:
print("column: ", end="")
else:
print("value: ", end="")
for j in range(s):
print(" ", representsparse[i][j], end="")
print()
using System;
class Program
{
static void Main()
{
// Input sparse array
int[,] sparse = { { 0, 0, 7, 0 },
{ 1, 0, 0, 0 },
{ 2, 0, 5, 0 },
{ 0, 8, 0, 4 } };
// Count non-zero elements in the sparse array
int s = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (sparse[i, j] != 0)
s++;
// Create representation array to store non-zero elements
int[,] representsparse = new int[3, s];
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (sparse[i, j] != 0)
{
representsparse[0, k] = i;
representsparse[1, k] = j;
representsparse[2, k] = sparse[i, j];
k++;
}
// Output representation of the sparse array using arrays
Console.WriteLine("Representation of Sparse array using arrays :\n");
for (int i = 0; i < 3; i++)
{
if (i == 0)
Console.Write("row: ");
else if (i == 1)
Console.Write("column: ");
else
Console.Write("value: ");
for (int j = 0; j < s; j++)
Console.Write(" " + representsparse[i, j]);
Console.WriteLine();
}
}
}
// This code is contributed by Monu Yadav
// JavaScript Implementation
// Implementation of array representation
// of the sparse array
const sparse = [
[0, 0, 7, 0],
[1, 0, 0, 0],
[2, 0, 5, 0],
[0, 8, 0, 4]
];
let s = 0;
for (let i = 0; i < 4; i++)
for (let j = 0; j < 4; j++)
if (sparse[i][j] !== 0)
s++;
const representsparse = [[], [], []];
let k = 0;
for (let i = 0; i < 4; i++)
for (let j = 0; j < 4; j++)
if (sparse[i][j] !== 0) {
representsparse[0][k] = i;
representsparse[1][k] = j;
representsparse[2][k] = sparse[i][j];
k++;
}
console.log("Representation of Sparse array using arrays : \n");
for (let i = 0; i < 3; i++) {
if (i === 0)
console.log("row: ");
else if (i === 1)
console.log("column: ");
else
console.log("value: ");
console.log(representsparse[i]);
}
// This code is contributed by Sakshi
Output
Representation of Sparse array using arrays : row: 0 1 2 2 3 3 column: 2 0 0 2 1 3 value: 7 1 2 5 8 4
Jagged Arrays
Jagged arrays, also known as “ragged arrays,” are multidimensional arrays in which each row can have a different length. In other words, a jagged array is an array of arrays, where the sub-arrays can have different lengths. This is in contrast to a regular (rectangular) multidimensional array, where all rows have the same number of elements.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n; // number of rows in the jagged array
// jagged array having n rows
vector<vector<int>> jagged_arr(n);
for (int i = 0; i < n; i++) {
// number of columns in current row
int k;
cin >> k;
for (int j = 0; j < k; j++) {
// taking input of i'th row and k'th column
int x;
cin >> x;
jagged_arr[i].push_back(x);
}
}
return 0;
}
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // Number of rows
ArrayList<ArrayList<Integer>> jaggedArr = new ArrayList<>();
for (int i = 0; i < n; i++) {
int k = scanner.nextInt(); // Number of columns in current row
ArrayList<Integer> row = new ArrayList<>();
for (int j = 0; j < k; j++) {
int x = scanner.nextInt(); // Input for i'th row and k'th column
row.add(x);
}
jaggedArr.add(row);
}
}
}
n = int(input("Enter the number of rows: "))
jagged_arr = []
for i in range(n):
k = int(input(f"Enter the number of columns in row {i + 1}: "))
row = []
for j in range(k):
x = int(input(f"Enter the value for row {i + 1}, column {j + 1}: "))
row.append(x)
jagged_arr.append(row)
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('Enter the number of rows in the jagged array: ', (n) => {
n = parseInt(n);
let jagged_arr = [];
function inputJaggedArray(index) {
if (index === n) {
console.log(jagged_arr);
rl.close();
return;
}
rl.question(`Enter the number of columns in row ${index + 1}: `, (k) => {
k = parseInt(k);
let row = [];
inputRowElements(index, k, 0, row);
});
}
function inputRowElements(rowIndex, k, j, row) {
if (j === k) {
jagged_arr.push(row);
inputJaggedArray(rowIndex + 1);
return;
}
rl.question(`Enter the element at row ${rowIndex + 1} and column ${j + 1}: `, (x) => {
x = parseInt(x);
row.push(x);
inputRowElements(rowIndex, k, j + 1, row);
});
}
inputJaggedArray(0);
});
Frequency Array:
Hashing using arrays, often referred to as “hash tables” or “hash maps,” is a data structure and technique used to efficiently store, retrieve, and manage key-value pairs. It involves using an array as the underlying data structure where data is stored based on a specific hashing function. Hashing using arrays is widely used in competitive programming.
If all the array values are within the range of the size of the array, then array can be used for hashing key-value pairs, providing O(1) complexity for each operation i.e. fetch and update.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> arr = {4, 2, 2, 5, 4, 4, 1, 5, 4};
vector<int> hash_table(arr.size(), 0);
for (int i = 0; i < arr.size(); i++) {
hash_table[arr[i]]++;
}
}
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
List<Integer> arr = Arrays.asList(4, 2, 2, 5, 4, 4, 1, 5, 4);
List<Integer> hashTable = new ArrayList<>(Collections.nCopies(arr.size(), 0));
for (int i = 0; i < arr.size(); i++) {
int element = arr.get(i);
hashTable.set(element, hashTable.get(element) + 1);
}
}
}
arr = [4, 2, 2, 5, 4, 4, 1, 5, 4]
hash_table = [0] * len(arr)
for element in arr:
hash_table[element] += 1
let arr = [4, 2, 2, 5, 4, 4, 1, 5, 4];
let hashTable = new Array(arr.length).fill(0);
for (let i = 0; i < arr.length; i++) {
hashTable[arr[i]]++;
}
Related articles on Competitive Programming (CP):