1. Arrays & Strings

Module 3· 9 min read· 12 Questions·In Progress

Foundation data structures - contiguous memory and character sequences

Data Structure Module - Learn how data is stored and organized

Arrays and Strings are the building blocks of programming. Every other data structure builds on these concepts!

What You'll Learn#

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

Understand how arrays store data in memory
Perform common array operations (access, insert, delete)
Work with 2D arrays (matrices)
Manipulate strings efficiently

1. Arrays - The Foundation#

What is an Array? (Simple Explanation)#

Think of an array like a row of lockers in a school:

Each locker has a number (index) - 0, 1, 2, 3...
Each locker can hold one item (value)
All lockers are side by side (contiguous memory)
You can go directly to locker #5 without checking lockers 0-4

Real-world examples:

Your contacts list on phone
A row of seats in a movie theater
Shopping cart items

Creating and Using Arrays#

Python

# Creating an array (list in Python)
fruits = ["apple", "banana", "cherry", "date"]
#         index 0   index 1   index 2   index 3

# ACCESS: Get item at index 2 - Super fast! O(1)
print(fruits[2])  # Output: "cherry"

# MODIFY: Change item at index 1
fruits[1] = "blueberry"
print(fruits)  # ["apple", "blueberry", "cherry", "date"]

# ADD: Append to end - Fast! O(1)
fruits.append("elderberry")

# INSERT: Add at specific position - Slow! O(n)
# Why slow? All elements after must shift right
fruits.insert(0, "avocado")  # Add at beginning

# DELETE: Remove by value - Slow! O(n)
fruits.remove("cherry")

# LENGTH: How many items? - Fast! O(1)
print(len(fruits))  # 5

Why Some Operations Are Slow?#

Inserting at the beginning (O(n)): Imagine inserting a person at the front of a queue - everyone must step back!

Diagram / Text

Before: [10, 20, 30, 40]
Insert 5 at position 0:
Step 1: [10, 20, 30, 40, _]  ← Make space
Step 2: [_, 10, 20, 30, 40]  ← Shift all right
Step 3: [5, 10, 20, 30, 40]  ← Insert 5

Time Complexity Summary#

Operation	Time	Why?
Access by index	O(1)	Direct jump to location
Search (unsorted)	O(n)	Must check each element (Linear Search)
Search (sorted)	O(log n)	Binary Search halves search space each step
Add at end	O(1)	Just add after last item
Add at beginning	O(n)	Shift all elements right
Delete	O(n)	Shift all elements left

Array Properties#

Homogeneous Elements — All elements must be of the same data type
Zero-based Indexing — First element is at index 0 (in most languages)
Contiguous Memory — Elements are stored adjacent to each other in memory
Fixed Size — Classic arrays have a fixed size declared at creation (dynamic arrays resize automatically)

Applications of Arrays#

Implementing sorting algorithms (Bubble Sort, Quick Sort, Merge Sort, etc.)
Building other data structures: Stacks, Queues, Heaps, Hash Tables
CPU scheduling algorithms
Storing image pixels (2D arrays)
Lookup tables for constant-time data retrieval

2. Memory Representation of Arrays#

1D Array — Address Calculation#

If an array starts at a base address, we can compute the memory location of any element:

Diagram / Text

Formula: LOC(A[k]) = Base + (k − LowerBound) × W

Where:
  Base  = base address of the array
  k     = index of the element
  W     = width (size in bytes) of each element

Example:

Diagram / Text

Base Address = 2000, Width = 4 bytes, Lower Bound = 0

LOC(A[3]) = 2000 + (3 − 0) × 4
          = 2000 + 12
          = 2012

Length of Array:

Diagram / Text

Length = Upper Bound − Lower Bound + 1

2D Array — Row Major vs Column Major#

Two ways to store a 2D array in linear memory:

Row Major Order (row by row — C, C++, Python, Java):

Diagram / Text

LOC(A[R,C]) = Base + W × ((R − RLB) × (CUB − CLB + 1) + (C − CLB))

Where:
  RLB = Row Lower Bound    CLB = Column Lower Bound
  CUB = Column Upper Bound  W = Width of each element

Column Major Order (column by column — Fortran, MATLAB):

Diagram / Text

LOC(A[R,C]) = Base + W × ((C − CLB) × (RUB − RLB + 1) + (R − RLB))

These formulas are frequently asked in technical exams!

3. Array Declaration (C Language)#

// Declaration
int a[100];        // Array of 100 integers

// Memory = sizeof(data_type) × length
// For int a[100]: Memory = 4 × 100 = 400 bytes

// Initialization at declaration
int a[4] = {34, 60, 93, 2};
int b[] = {2, 3, 4, 5};      // Size is optional if initialized
float c[] = {-4, 6.8, 60};

// Important:
// 1. If initialized at declaration, dimension is optional
// 2. If not initialized, elements contain garbage values

4. 2D Arrays (Matrices)#

A 2D array is like a table with rows and columns - think of Excel spreadsheet!

Python

# Creating a 3x3 matrix
matrix = [
    [1, 2, 3],    # Row 0
    [4, 5, 6],    # Row 1
    [7, 8, 9]     # Row 2
]
#   Col0 Col1 Col2

# Access element at row 1, column 2
print(matrix[1][2])  # Output: 6 (row 1, col 2)

# Traverse all elements (row by row)
for row in range(3):
    for col in range(3):
        print(matrix[row][col], end=" ")
    print()  # New line after each row

# Output:
# 1 2 3
# 4 5 6
# 7 8 9

Common uses:

Game boards (chess, tic-tac-toe)
Image pixels
Maps and grids

5. Strings - Array of Characters#

A string is essentially an array of characters!

Python

# Strings in Python
name = "Hello World"

# Access character (just like array!)
print(name[0])    # 'H'
print(name[6])    # 'W'

# Get length
print(len(name))  # 11 (includes space)

# Slicing - Get part of string
print(name[0:5])   # "Hello"
print(name[6:])    # "World"

# IMPORTANT: Strings are IMMUTABLE in Python
# This means you can't modify them directly
# name[0] = 'h'  ← This would cause ERROR!

# Instead, create a new string:
name_lower = name.lower()  # "hello world"

Common String Operations#

Python

text = "hello world"

# Find position of substring
position = text.find("world")  # Returns 6

# Replace text
new_text = text.replace("world", "python")  # "hello python"

# Split into list
words = text.split(" ")  # ["hello", "world"]

# Join list into string
joined = "-".join(words)  # "hello-world"

# Check start/end
text.startswith("hello")  # True
text.endswith("world")    # True

Key Takeaways#

Concept	Array	String
Access	O(1) - Instant	O(1) - Instant
Modify	O(1) - Can change	O(n) - Create new
Insert	O(n) - Shift needed	O(n) - Create new
Search	O(n) - Check each	O(n) - Check each

Remember:

Arrays = Mutable (can change)
Strings = Immutable (cannot change in Python)

TL;DR - Quick Recall#

One-liner for each concept:

Concept	Key Takeaway
Array	Contiguous memory for O(1) index access, but O(n) insertion/deletion.
Sparse Matrix	Mostly zeros; saved memory by storing as (Row, Column, Value) triplets.
String	An array of characters; immutable in languages like Python/Java.
Matrices	2D Arrays (rows and columns); used for maps, boards, and mathematical representations.
Memory	Arrays have a fixed size natively; Dynamic Arrays resize automatically under the hood (amortized O(1) append).

Essential Code Snippets:

Python

# Finding in an array
has_five = 5 in my_array  # O(n) search

# Sparse Matrix (Triplet)
sparse = [
    (0, 2, 15),  # Row 0, Col 2 = 15
    (1, 1, 22)   # Row 1, Col 1 = 22
]

# String tricks
reversed_str = my_str[::-1]
words = my_str.split(" ")

The Golden Rules:

Remember that Array insertion at the beginning is O(n) because every element shifts!
Two pointers and Sliding Window are the most common array patterns.
Because Strings are immutable (Python/Java), string concatenation inside a loop is often O(n²) unless using .join().

Additional Resources#

Video Courses:

NeetCode - Arrays & Hashing - Excellent LeetCode preparations
Introduction to Data Structures & Algorithms - Deep dive for university exams

Articles & Visualizations:

VisuAlgo - Array - Interactive array operations
GeeksforGeeks - Sparse Matrix - Great for exam theory

Practice Problems:

LeetCode 1: Two Sum
LeetCode 217: Contains Duplicate
LeetCode 242: Valid Anagram

Practice Quiz

Test your understanding with step-by-step solutions

Practice Quiz

12 questions · 90s per question

Each question has a 90-second time limit. Unanswered questions will be auto-submitted when time runs out.

Module 3· 9 min read· 12 Questions·In Progress

1. Arrays & Strings

Foundation data structures - contiguous memory and character sequences

Data Structure Module - Learn how data is stored and organized

Arrays and Strings are the building blocks of programming. Every other data structure builds on these concepts!

What You'll Learn#

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

Understand how arrays store data in memory
Perform common array operations (access, insert, delete)
Work with 2D arrays (matrices)
Manipulate strings efficiently

1. Arrays - The Foundation#

What is an Array? (Simple Explanation)#

Think of an array like a row of lockers in a school:

Each locker has a number (index) - 0, 1, 2, 3...
Each locker can hold one item (value)
All lockers are side by side (contiguous memory)
You can go directly to locker #5 without checking lockers 0-4

Real-world examples:

Your contacts list on phone
A row of seats in a movie theater
Shopping cart items

Creating and Using Arrays#

Python

# Creating an array (list in Python)
fruits = ["apple", "banana", "cherry", "date"]
#         index 0   index 1   index 2   index 3

# ACCESS: Get item at index 2 - Super fast! O(1)
print(fruits[2])  # Output: "cherry"

# MODIFY: Change item at index 1
fruits[1] = "blueberry"
print(fruits)  # ["apple", "blueberry", "cherry", "date"]

# ADD: Append to end - Fast! O(1)
fruits.append("elderberry")

# INSERT: Add at specific position - Slow! O(n)
# Why slow? All elements after must shift right
fruits.insert(0, "avocado")  # Add at beginning

# DELETE: Remove by value - Slow! O(n)
fruits.remove("cherry")

# LENGTH: How many items? - Fast! O(1)
print(len(fruits))  # 5

Why Some Operations Are Slow?#

Inserting at the beginning (O(n)): Imagine inserting a person at the front of a queue - everyone must step back!

Diagram / Text

Before: [10, 20, 30, 40]
Insert 5 at position 0:
Step 1: [10, 20, 30, 40, _]  ← Make space
Step 2: [_, 10, 20, 30, 40]  ← Shift all right
Step 3: [5, 10, 20, 30, 40]  ← Insert 5

Time Complexity Summary#

Operation	Time	Why?
Access by index	O(1)	Direct jump to location
Search (unsorted)	O(n)	Must check each element (Linear Search)
Search (sorted)	O(log n)	Binary Search halves search space each step
Add at end	O(1)	Just add after last item
Add at beginning	O(n)	Shift all elements right
Delete	O(n)	Shift all elements left

Array Properties#

Homogeneous Elements — All elements must be of the same data type
Zero-based Indexing — First element is at index 0 (in most languages)
Contiguous Memory — Elements are stored adjacent to each other in memory
Fixed Size — Classic arrays have a fixed size declared at creation (dynamic arrays resize automatically)

Applications of Arrays#

Implementing sorting algorithms (Bubble Sort, Quick Sort, Merge Sort, etc.)
Building other data structures: Stacks, Queues, Heaps, Hash Tables
CPU scheduling algorithms
Storing image pixels (2D arrays)
Lookup tables for constant-time data retrieval

2. Memory Representation of Arrays#

1D Array — Address Calculation#

If an array starts at a base address, we can compute the memory location of any element:

Diagram / Text

Formula: LOC(A[k]) = Base + (k − LowerBound) × W

Where:
  Base  = base address of the array
  k     = index of the element
  W     = width (size in bytes) of each element

Example:

Diagram / Text

Base Address = 2000, Width = 4 bytes, Lower Bound = 0

LOC(A[3]) = 2000 + (3 − 0) × 4
          = 2000 + 12
          = 2012

Length of Array:

Diagram / Text

Length = Upper Bound − Lower Bound + 1

2D Array — Row Major vs Column Major#

Two ways to store a 2D array in linear memory:

Row Major Order (row by row — C, C++, Python, Java):

Diagram / Text

LOC(A[R,C]) = Base + W × ((R − RLB) × (CUB − CLB + 1) + (C − CLB))

Where:
  RLB = Row Lower Bound    CLB = Column Lower Bound
  CUB = Column Upper Bound  W = Width of each element

Column Major Order (column by column — Fortran, MATLAB):

Diagram / Text

LOC(A[R,C]) = Base + W × ((C − CLB) × (RUB − RLB + 1) + (R − RLB))

These formulas are frequently asked in technical exams!

3. Array Declaration (C Language)#

// Declaration
int a[100];        // Array of 100 integers

// Memory = sizeof(data_type) × length
// For int a[100]: Memory = 4 × 100 = 400 bytes

// Initialization at declaration
int a[4] = {34, 60, 93, 2};
int b[] = {2, 3, 4, 5};      // Size is optional if initialized
float c[] = {-4, 6.8, 60};

// Important:
// 1. If initialized at declaration, dimension is optional
// 2. If not initialized, elements contain garbage values

4. 2D Arrays (Matrices)#

A 2D array is like a table with rows and columns - think of Excel spreadsheet!

Python

# Creating a 3x3 matrix
matrix = [
    [1, 2, 3],    # Row 0
    [4, 5, 6],    # Row 1
    [7, 8, 9]     # Row 2
]
#   Col0 Col1 Col2

# Access element at row 1, column 2
print(matrix[1][2])  # Output: 6 (row 1, col 2)

# Traverse all elements (row by row)
for row in range(3):
    for col in range(3):
        print(matrix[row][col], end=" ")
    print()  # New line after each row

# Output:
# 1 2 3
# 4 5 6
# 7 8 9

Common uses:

Game boards (chess, tic-tac-toe)
Image pixels
Maps and grids

5. Strings - Array of Characters#

A string is essentially an array of characters!

Python

# Strings in Python
name = "Hello World"

# Access character (just like array!)
print(name[0])    # 'H'
print(name[6])    # 'W'

# Get length
print(len(name))  # 11 (includes space)

# Slicing - Get part of string
print(name[0:5])   # "Hello"
print(name[6:])    # "World"

# IMPORTANT: Strings are IMMUTABLE in Python
# This means you can't modify them directly
# name[0] = 'h'  ← This would cause ERROR!

# Instead, create a new string:
name_lower = name.lower()  # "hello world"

Common String Operations#

Python

text = "hello world"

# Find position of substring
position = text.find("world")  # Returns 6

# Replace text
new_text = text.replace("world", "python")  # "hello python"

# Split into list
words = text.split(" ")  # ["hello", "world"]

# Join list into string
joined = "-".join(words)  # "hello-world"

# Check start/end
text.startswith("hello")  # True
text.endswith("world")    # True

Key Takeaways#

Concept	Array	String
Access	O(1) - Instant	O(1) - Instant
Modify	O(1) - Can change	O(n) - Create new
Insert	O(n) - Shift needed	O(n) - Create new
Search	O(n) - Check each	O(n) - Check each

Remember:

Arrays = Mutable (can change)
Strings = Immutable (cannot change in Python)

TL;DR - Quick Recall#

One-liner for each concept:

Concept	Key Takeaway
Array	Contiguous memory for O(1) index access, but O(n) insertion/deletion.
Sparse Matrix	Mostly zeros; saved memory by storing as (Row, Column, Value) triplets.
String	An array of characters; immutable in languages like Python/Java.
Matrices	2D Arrays (rows and columns); used for maps, boards, and mathematical representations.
Memory	Arrays have a fixed size natively; Dynamic Arrays resize automatically under the hood (amortized O(1) append).

Essential Code Snippets:

Python

# Finding in an array
has_five = 5 in my_array  # O(n) search

# Sparse Matrix (Triplet)
sparse = [
    (0, 2, 15),  # Row 0, Col 2 = 15
    (1, 1, 22)   # Row 1, Col 1 = 22
]

# String tricks
reversed_str = my_str[::-1]
words = my_str.split(" ")

The Golden Rules:

Remember that Array insertion at the beginning is O(n) because every element shifts!
Two pointers and Sliding Window are the most common array patterns.
Because Strings are immutable (Python/Java), string concatenation inside a loop is often O(n²) unless using .join().

Additional Resources#

Video Courses:

NeetCode - Arrays & Hashing - Excellent LeetCode preparations
Introduction to Data Structures & Algorithms - Deep dive for university exams

Articles & Visualizations:

VisuAlgo - Array - Interactive array operations
GeeksforGeeks - Sparse Matrix - Great for exam theory

Practice Problems:

LeetCode 1: Two Sum
LeetCode 217: Contains Duplicate
LeetCode 242: Valid Anagram

Practice Quiz

Test your understanding with step-by-step solutions

Practice Quiz

12 questions · 90s per question

Each question has a 90-second time limit. Unanswered questions will be auto-submitted when time runs out.