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):
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)