Chapter 7: Arrays and Strings: The Building Blocks

Introduction: The Foundation of Data

Welcome back, aspiring DSA master! In the previous chapters, we laid crucial groundwork, setting up our development environment, diving into TypeScript fundamentals, and understanding the powerful concept of Big-O notation for analyzing algorithm efficiency. Now, it’s time to get our hands dirty with the most fundamental and widely used data structures: Arrays and Strings.

Think of arrays and strings as the LEGO bricks of programming. Almost every complex data structure or algorithm you’ll encounter is built upon these simple, yet incredibly powerful, constructs. Mastering their properties, common operations, and performance characteristics is absolutely essential. It’s like learning to walk before you can run – these are your first confident steps into the world of Data Structures and Algorithms!

In this chapter, we’ll explore what arrays and strings are, how TypeScript helps us work with them safely and efficiently, and the time complexity of their most common operations. We’ll break down each concept into “baby steps,” provide clear TypeScript code examples, and challenge you with practical exercises to solidify your understanding. By the end, you’ll have a rock-solid foundation for tackling more advanced topics. Let’s dive in!

Understanding Arrays: Ordered Collections

An array is a fundamental data structure that stores a collection of items in a specific order. Imagine a row of mailboxes, each with a unique number. You can put a letter in any mailbox, and you know exactly where to find it by its number. That’s essentially what an array does!

Key Characteristics of Arrays

Ordered Collection: Elements in an array maintain a specific sequence. The order in which you add them is generally preserved.
Indexed Access: Each element in an array is assigned a unique numerical index, starting from 0. This allows for very fast (constant time) access to any element if you know its index.
Contiguous Memory (Conceptual): In many low-level languages, arrays are stored in contiguous blocks of memory. While JavaScript/TypeScript arrays are more abstract and dynamic, the idea of quick access via an index remains central.
Dynamic Sizing in TypeScript/JavaScript: Unlike some languages where arrays have a fixed size defined at creation, arrays in TypeScript (which are JavaScript arrays under the hood) are dynamic. This means they can grow or shrink as needed. When an array needs to grow beyond its current allocated space, JavaScript might internally allocate a new, larger array and copy all existing elements over. This resizing operation can be costly, but it’s usually optimized to happen infrequently, leading to “amortized” constant time performance for adding elements to the end.
Homogeneous or Heterogeneous: While TypeScript encourages type safety, allowing you to declare an array that holds only numbers (number[]) or only strings (string[]), JavaScript arrays can technically hold elements of different types (heterogeneous). Using TypeScript, however, we primarily work with typed arrays for better code predictability and error prevention.

Common Array Operations and Their Complexity

Let’s look at the most common things we do with arrays and how efficient these operations are, using our Big-O notation from Chapter 6.

1. Accessing an Element

Description: Retrieving an element at a specific index.
Example: Getting the item at index 2.
Time Complexity: O(1) (Constant Time). This is incredibly fast because the computer can directly calculate the memory location of the element using its index.

2. Adding an Element

To the End (push):
- Description: Appending a new element to the end of the array.
- Time Complexity: O(1) (Amortized Constant Time). Most of the time, there’s space at the end, so it’s fast. Occasionally, if the array needs to resize, it becomes O(N) (linear), but these O(N) operations are rare enough that the average cost over many push operations is O(1).
To the Beginning (unshift):
- Description: Adding a new element to the start of the array.
- Time Complexity: O(N) (Linear Time). When you add an element to the beginning, all existing elements need to be shifted one position to make space. If there are N elements, N shifts are required.
Into the Middle (splice):
- Description: Inserting an element at a specific index within the array.
- Time Complexity: O(N) (Linear Time). Similar to unshift, elements after the insertion point need to be shifted to make room.

3. Removing an Element

From the End (pop):
- Description: Removing the last element from the array.
- Time Complexity: O(1) (Constant Time). No other elements need to be moved.
From the Beginning (shift):
- Description: Removing the first element from the array.
- Time Complexity: O(N) (Linear Time). All remaining elements need to be shifted one position to the left to fill the gap.
From the Middle (splice):
- Description: Removing an element at a specific index within the array.
- Time Complexity: O(N) (Linear Time). Elements after the removed item need to be shifted to close the gap.

4. Iterating Through Elements

Description: Visiting each element in the array once.
Time Complexity: O(N) (Linear Time). You have to touch N elements, so the time taken grows proportionally with the number of elements.

When to Use Arrays?

Arrays are excellent when:

You need to store an ordered list of items.
You frequently need to access elements by their index.
You primarily add/remove elements from the end.

Understanding Strings: Sequences of Characters

A string is essentially a sequence of characters. In TypeScript and JavaScript, strings are used to represent text. You can think of a string as a specialized array where each “element” is a character.

Key Characteristics of Strings

Sequence of Characters: Strings are collections of characters, like letters, numbers, symbols, and spaces, arranged in a specific order.
Indexed Access: Just like arrays, characters in a string can be accessed by their index, starting from 0.
Immutability (Crucial!): This is a very important concept for strings in TypeScript/JavaScript. Once a string is created, its content cannot be changed. Any operation that appears to modify a string (like toUpperCase() or concat()) actually returns a new string with the changes, leaving the original string untouched. This immutability simplifies reasoning about string values and can prevent unexpected side effects.
Fixed-Size (Effectively): Because strings are immutable, their “size” (length) is fixed once created. Operations that change length (like concatenation) create new strings.

Common String Operations and Their Complexity

Many string operations are similar to array operations, but with the immutability constraint.

1. Accessing a Character

Description: Retrieving a character at a specific index.
Example: Getting the character at index 0.
Time Complexity: O(1) (Constant Time). Similar to array element access.

2. Concatenation

Description: Joining two or more strings together to form a new string.
Example: "Hello" + "World".
Time Complexity: O(N + M) (Linear Time). If you’re joining a string of length N with a string of length M, a new string of length N+M needs to be created and filled, requiring time proportional to its new length.

3. Substring Extraction

Description: Creating a new string containing a portion of an existing string.
Example: Getting "World" from "HelloWorld".
Time Complexity: O(L) (Linear Time). Where L is the length of the extracted substring. A new string needs to be created and populated.

4. Searching for a Substring

Description: Finding if one string exists within another, or finding its starting index.
Example: myString.indexOf("search").
Time Complexity: O(N * M) (Worst Case, Naive Algorithm). Where N is the length of the main string and M is the length of the substring being searched for. More optimized algorithms exist (like KMP), but built-in methods often perform well for typical cases. For simple includes or indexOf, it’s usually O(N) in practice, as M is often small.

5. Iterating Through Characters

Description: Visiting each character in the string once.
Time Complexity: O(N) (Linear Time). Where N is the length of the string.

When to Use Strings?

Strings are essential when:

You need to work with textual data.
You need an ordered sequence of characters.
The immutability property is beneficial for preventing accidental changes.

Step-by-Step Implementation in TypeScript

Let’s put these concepts into practice with some TypeScript code! We’ll start with a fresh file, src/chapter7.ts, in our project.

Setting Up Our File

First, ensure you have a src folder in your project root. Inside src, create chapter7.ts.

// src/chapter7.ts

console.log("Chapter 7: Arrays and Strings - The Building Blocks");

// We'll add our code here!

To run this, compile it and then execute with Node.js: npx ts-node src/chapter7.ts (or tsc src/chapter7.ts && node src/chapter7.js)

You should see: Chapter 7: Arrays and Strings - The Building Blocks

Working with Arrays in TypeScript

Step 1: Declaring Arrays

In TypeScript, we can declare arrays with clear type annotations, which is one of TypeScript’s superpowers!

// src/chapter7.ts (add to the file)

// An array of numbers
let numbers: number[] = [10, 20, 30, 40, 50];
console.log("Initial numbers array:", numbers); // Output: [ 10, 20, 30, 40, 50 ]

// An array of strings
let fruits: string[] = ["Apple", "Banana", "Cherry"];
console.log("Initial fruits array:", fruits); // Output: [ 'Apple', 'Banana', 'Cherry' ]

// An empty array of a specific type
let emptyArray: boolean[] = [];
console.log("Empty boolean array:", emptyArray); // Output: []

// You can also use the Array<Type> generic syntax, which is equivalent
let scores: Array<number> = [95, 88, 72];
console.log("Scores array (generic syntax):", scores); // Output: [ 95, 88, 72 ]

Explanation:

let numbers: number[] = [10, 20, 30, 40, 50]; declares a variable numbers that must hold an array where every element is a number. If you tried to add a string to numbers, TypeScript would give you a compile-time error! This is fantastic for catching mistakes early.
The Array<number> syntax is another way to declare the same type of array. Choose whichever you find more readable.

Step 2: Accessing Array Elements

Accessing elements by their index is straightforward and O(1).

// src/chapter7.ts (add to the file)

console.log("\n--- Array Access ---");
console.log("First number:", numbers[0]); // Output: 10
console.log("Third fruit:", fruits[2]);   // Output: Cherry

// Accessing an out-of-bounds index returns `undefined`
console.log("Number at index 100 (non-existent):", numbers[100]); // Output: undefined

Explanation:

numbers[0] gives us the first element (remember, 0-indexed!).
Attempting to access an index that doesn’t exist won’t throw an error at runtime but will return undefined. TypeScript will warn you if you try to access an index that might be out of bounds if it can determine it statically.

Step 3: Modifying Arrays (Adding/Removing Elements)

Let’s see the dynamic nature of JavaScript/TypeScript arrays in action.

// src/chapter7.ts (add to the file)

console.log("\n--- Array Modification ---");

// Add to the end (push) - O(1) amortized
fruits.push("Date");
console.log("Fruits after push:", fruits); // Output: [ 'Apple', 'Banana', 'Cherry', 'Date' ]

// Remove from the end (pop) - O(1)
let lastFruit = fruits.pop();
console.log("Removed fruit (pop):", lastFruit); // Output: Date
console.log("Fruits after pop:", fruits);       // Output: [ 'Apple', 'Banana', 'Cherry' ]

// Add to the beginning (unshift) - O(N)
fruits.unshift("Grape");
console.log("Fruits after unshift:", fruits); // Output: [ 'Grape', 'Apple', 'Banana', 'Cherry' ]

// Remove from the beginning (shift) - O(N)
let firstFruit = fruits.shift();
console.log("Removed fruit (shift):", firstFruit); // Output: Grape
console.log("Fruits after shift:", fruits);         // Output: [ 'Apple', 'Banana', 'Cherry' ]

// Remove/Insert from/into the middle (splice) - O(N)
// splice(startIndex, deleteCount, item1, item2, ...)
fruits.splice(1, 1); // Remove 1 element starting from index 1 (Banana)
console.log("Fruits after splice (remove Banana):", fruits); // Output: [ 'Apple', 'Cherry' ]

fruits.splice(1, 0, "Mango", "Orange"); // Insert Mango and Orange at index 1, delete 0 elements
console.log("Fruits after splice (insert Mango, Orange):", fruits); // Output: [ 'Apple', 'Mango', 'Orange', 'Cherry' ]

Explanation:

push() and pop() are generally preferred for performance when working with the ends of arrays.
unshift() and shift() are less efficient because they require re-indexing all subsequent elements.
splice() is powerful but can be complex. It allows you to remove elements, insert elements, or both, starting from a specific index.

Step 4: Iterating Over Arrays

You’ll often need to process every item in an array.

// src/chapter7.ts (add to the file)

console.log("\n--- Array Iteration ---");

// Using a for...of loop (modern and concise)
console.log("Iterating with for...of:");
for (const num of numbers) {
    console.log(num * 2); // Double each number
}
// Output: 20, 40, 60, 80, 100

// Using forEach (a higher-order function)
console.log("Iterating with forEach:");
fruits.forEach((fruit, index) => {
    console.log(`Fruit ${index + 1}: ${fruit}`);
});
// Output:
// Fruit 1: Apple
// Fruit 2: Mango
// Fruit 3: Orange
// Fruit 4: Cherry

// Using a traditional for loop (useful when you need the index for more complex logic)
console.log("Iterating with traditional for loop:");
for (let i = 0; i < fruits.length; i++) {
    console.log(`Fruit at index ${i}: ${fruits[i]}`);
}

Explanation:

for...of is excellent for simply iterating over values.
forEach is a method available on arrays that takes a callback function. It’s concise and widely used.
The traditional for loop gives you explicit control over the index, which can be useful for algorithms that require index-based manipulation.

Working with Strings in TypeScript

Step 1: Declaring Strings

Strings are defined using single quotes, double quotes, or backticks (template literals).

// src/chapter7.ts (add to the file)

console.log("\n--- String Basics ---");

let greeting: string = "Hello, TypeScript!";
let name: string = 'Alice';
let combined: string = `My name is ${name}. ${greeting}`; // Template literal for easy interpolation

console.log("Greeting:", greeting); // Output: Hello, TypeScript!
console.log("Name:", name);         // Output: Alice
console.log("Combined:", combined); // Output: My name is Alice. Hello, TypeScript!

Explanation:

let greeting: string = "Hello, TypeScript!"; clearly states that greeting is a string.
Template literals (using backticks `) are super handy for embedding expressions (${name}) directly within the string.

Step 2: Accessing Characters

Strings can be treated like read-only arrays of characters for access.

// src/chapter7.ts (add to the file)

console.log("\n--- String Character Access ---");

let word: string = "TypeScript";
console.log("First character:", word[0]); // Output: T
console.log("Fifth character:", word[4]); // Output: S

// Like arrays, out-of-bounds access returns undefined
console.log("Character at index 20:", word[20]); // Output: undefined

Explanation:

word[0] gives you the character at the first position.
Remember, strings are immutable! You cannot do word[0] = 't'; – TypeScript will throw an error, and even in plain JavaScript, it would silently fail to change the string.

Step 3: String Operations (Returning New Strings)

All string “modification” methods return a new string.

// src/chapter7.ts (add to the file)

console.log("\n--- String Operations ---");

let originalString: string = "  Hello World!   ";

// Immutability in action:
let upperCaseString = originalString.toUpperCase();
console.log("Original:", originalString);    // Output:   Hello World!
console.log("Uppercase:", upperCaseString); // Output:   HELLO WORLD!

// Trim whitespace
let trimmedString = originalString.trim();
console.log("Trimmed:", trimmedString); // Output: Hello World!

// Substrings (slice, substring, substr - slice is generally preferred)
let slicedPart = trimmedString.slice(0, 5); // From index 0 up to (but not including) index 5
console.log("Sliced (0, 5):", slicedPart); // Output: Hello

let substringPart = trimmedString.substring(6, 11); // From index 6 up to (but not including) index 11
console.log("Substring (6, 11):", substringPart); // Output: World

// Concatenation
let greeting2: string = "Good";
let message2: string = "Morning";
let fullMessage: string = greeting2 + " " + message2 + "!";
console.log("Concatenated:", fullMessage); // Output: Good Morning!

// Searching
console.log("Contains 'World'?", trimmedString.includes("World")); // Output: true
console.log("Index of 'World':", trimmedString.indexOf("World"));  // Output: 6
console.log("Index of 'xyz':", trimmedString.indexOf("xyz"));      // Output: -1 (not found)

// Splitting a string into an array
let sentence: string = "TypeScript is awesome!";
let wordsArray: string[] = sentence.split(" "); // Split by space
console.log("Words array:", wordsArray); // Output: [ 'TypeScript', 'is', 'awesome!' ]

// Joining an array into a string
let joinedSentence: string = wordsArray.join("-");
console.log("Joined sentence:", joinedSentence); // Output: TypeScript-is-awesome!

Explanation:

Notice how originalString remains unchanged throughout. toUpperCase(), trim(), slice(), substring(), concat() (implicitly via +) all return new strings.
slice(startIndex, endIndex) extracts a portion of the string. endIndex is exclusive.
indexOf() returns the starting index of the first occurrence of a substring, or -1 if not found.
split() is incredibly useful for parsing strings into arrays of substrings.
join() is the inverse of split(), taking an array of strings and concatenating them with a specified separator.

Mini-Challenge: Array & String Manipulators

It’s your turn to code! These challenges will help you apply what you’ve learned.

Challenge 1: Filter Even Numbers (Arrays)

Task: Write a TypeScript function named filterEvenNumbers that takes an array of numbers (number[]) as input. The function should return a new array containing only the even numbers from the input array, without modifying the original array.

Hint: Think about array iteration and the modulo operator (%) to check for evenness. Array methods like filter() can be very elegant here, but try a for...of loop first if filter() feels too advanced right now.

Click for Solution Hint!

You'll want to create an empty array to store your results. Then, iterate through the input array. For each number, check if `number % 2 === 0`. If it is, add it to your results array.

// Add your solution for Challenge 1 here
function filterEvenNumbers(numbers: number[]): number[] {
    // Your code here
    const evenNumbers: number[] = [];
    for (const num of numbers) {
        if (num % 2 === 0) {
            evenNumbers.push(num);
        }
    }
    return evenNumbers;
}

// Test cases for Challenge 1
console.log("\n--- Challenge 1: Filter Even Numbers ---");
const testNumbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const evens = filterEvenNumbers(testNumbers);
console.log("Original array:", testNumbers); // Should be unchanged: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log("Even numbers:", evens);         // Should be: [2, 4, 6, 8, 10]

const emptyTest: number[] = [];
console.log("Empty array test:", filterEvenNumbers(emptyTest)); // Should be: []

const oddTest = [1, 3, 5];
console.log("Odd array test:", filterEvenNumbers(oddTest)); // Should be: []

Challenge 2: Reverse a String (Strings)

Task: Write a TypeScript function named reverseString that takes a string (string) as input. The function should return a new string that is the reverse of the input string.

Hint: Remember that strings are immutable. You can convert a string to an array of characters, manipulate the array, and then convert it back to a string.

Click for Solution Hint!

Consider using the `split('')` method to turn the string into an array of characters. Then, the `reverse()` array method might be useful. Finally, `join('')` to turn it back into a string.

// Add your solution for Challenge 2 here
function reverseString(inputString: string): string {
    // Your code here
    // Step 1: Split the string into an array of characters
    const charArray: string[] = inputString.split('');

    // Step 2: Reverse the array of characters
    charArray.reverse();

    // Step 3: Join the array of characters back into a string
    return charArray.join('');
}

// Test cases for Challenge 2
console.log("\n--- Challenge 2: Reverse a String ---");
console.log("Hello World! reversed:", reverseString("Hello World!")); // Should be: !dlroW olleH
console.log("TypeScript reversed:", reverseString("TypeScript"));   // Should be: tpircSepyT
console.log("A reversed:", reverseString("A"));                     // Should be: A
console.log("Empty string reversed:", reverseString(""));           // Should be:

How did you do? Don’t worry if you needed the hints! The goal is to learn and experiment. The key is understanding why these operations work the way they do and how to combine them.

Common Pitfalls & Troubleshooting

Even though arrays and strings seem simple, there are some common traps developers fall into.

Off-by-One Errors (0-Indexing):
- Pitfall: Forgetting that arrays and strings are 0-indexed. This leads to issues when iterating (for (let i = 0; i <= arr.length; i++) is wrong, should be < arr.length) or accessing the last element (arr[arr.length] is wrong, should be arr[arr.length - 1]).
- Troubleshooting: Always double-check your loop conditions and index calculations. Use arr.length - 1 for the last element. Practice writing loops from memory.
Modifying Arrays While Iterating (Using for loop with splice/shift/pop):
- Pitfall: If you use a traditional for loop and modify the array’s length (e.g., splice to remove elements, shift, pop) while iterating forward, you can skip elements or cause unexpected behavior because the indices shift.
- Troubleshooting:
  - When removing elements, iterate backwards (for (let i = arr.length - 1; i >= 0; i--)).
  - Or, create a new array with the desired elements (e.g., using filter() or map()). This is often cleaner and safer.
  - Avoid shift() and unshift() for performance reasons if you’re frequently modifying the beginning of large arrays; consider a LinkedList (which we’ll cover later) instead.
Forgetting String Immutability:
- Pitfall: Expecting myString.toUpperCase() to change myString in place. This is a common mistake for those coming from languages where strings are mutable.
- Troubleshooting: Always assign the result of a string method back to a variable (or the original variable if that’s your intent): myString = myString.toUpperCase();.
Reference vs. Value (for Arrays):
- Pitfall: When you assign one array to another variable (let arr2 = arr1;), arr2 doesn’t get a copy of arr1; it gets a reference to the same array in memory. Modifying arr2 will also modify arr1.
- Troubleshooting: To create a true copy of an array, use methods like slice(), the spread operator (...), or Array.from():
```
let original = [1, 2, 3];
let copy = [...original]; // Creates a shallow copy
copy.push(4);
console.log(original); // [1, 2, 3] - original is unchanged
console.log(copy);     // [1, 2, 3, 4]
```
- This is a crucial concept for preventing unintended side effects in your programs.

Summary: Your Building Blocks Are Ready!

Phew! We’ve covered a lot of ground in this chapter, but these are truly foundational concepts that will serve you throughout your DSA journey.

Here are the key takeaways:

Arrays are ordered collections of elements, accessed by a numerical index starting from 0.
In TypeScript/JavaScript, arrays are dynamic, meaning they can grow and shrink.
Array Operation Complexities:
- Accessing by index: O(1)
- Adding/Removing from end (push/pop): O(1) (amortized)
- Adding/Removing from beginning/middle (unshift/shift/splice): O(N)
- Iterating: O(N)
Strings are immutable sequences of characters. Any operation that seems to change a string actually returns a new string.
String Operation Complexities:
- Accessing character by index: O(1)
- Concatenation: O(N + M)
- Substring extraction: O(L)
- Searching: O(N * M) (worst case), often O(N) in practice.
- Iterating: O(N)
TypeScript provides excellent type safety for arrays and strings, helping you catch errors early.
Be mindful of common pitfalls like 0-indexing, modifying arrays during iteration, and string immutability. Always create copies when you intend to modify an array independently.

You now have a solid understanding of these fundamental building blocks. Arrays and strings are not just abstract concepts; they are everywhere in real-world applications! Think about how a list of user comments, a sequence of characters in a search bar, or a list of items in a shopping cart are all handled using these structures.

What’s next? In the upcoming chapters, we’ll build upon this knowledge to explore more complex linear data structures like Linked Lists, Stacks, and Queues, which offer different trade-offs in terms of performance and use cases. Keep practicing, keep coding, and keep asking “why”!

References

TypeScript Handbook - Arrays: https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#arrays
TypeScript Handbook - String Literals: https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#string-literals
MDN Web Docs - Array: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
MDN Web Docs - String: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String
Node.js v24.13.0 LTS Documentation: https://nodejs.org/docs/v24.13.0/api/ (For general Node.js environment context)

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.

Chapter 7: Arrays and Strings: The Building Blocks

Table of Contents

Introduction: The Foundation of Data

Understanding Arrays: Ordered Collections

Key Characteristics of Arrays

Common Array Operations and Their Complexity

1. Accessing an Element

2. Adding an Element

3. Removing an Element

4. Iterating Through Elements

When to Use Arrays?

Understanding Strings: Sequences of Characters

Key Characteristics of Strings

Common String Operations and Their Complexity

1. Accessing a Character

2. Concatenation

3. Substring Extraction

4. Searching for a Substring

5. Iterating Through Characters

When to Use Strings?

Step-by-Step Implementation in TypeScript

Setting Up Our File

Working with Arrays in TypeScript

Step 1: Declaring Arrays

Step 2: Accessing Array Elements

Step 3: Modifying Arrays (Adding/Removing Elements)

Step 4: Iterating Over Arrays

Working with Strings in TypeScript

Step 1: Declaring Strings

Step 2: Accessing Characters

Step 3: String Operations (Returning New Strings)

Mini-Challenge: Array & String Manipulators

Challenge 1: Filter Even Numbers (Arrays)

Challenge 2: Reverse a String (Strings)

Common Pitfalls & Troubleshooting

Summary: Your Building Blocks Are Ready!

References