Learning Paths/Foundations/Arrays & Strings

Arrays & Strings

Arrays and strings are fundamental data structures that form the building blocks of most algorithms. This module covers the essential concepts, operations, and common patterns for working with arrays and strings.

Introduction to Arrays

An array is a collection of elements stored at contiguous memory locations. It is the simplest data structure where each element can be accessed directly using its index.

Key Characteristics

Fixed size (in most languages)
Homogeneous elements (same data type)
Random access (O(1) time complexity)
Contiguous memory allocation

Common Operations

Operation	Time Complexity	Description
Access	O(1)	Accessing an element at a given index
Search	O(n)	Finding an element in an unsorted array
Insert	O(n)	Inserting an element (may require shifting elements)
Delete	O(n)	Deleting an element (may require shifting elements)

Introduction to Strings

A string is a sequence of characters. In most programming languages, strings are implemented as arrays of characters with special properties and methods.

Key Characteristics

Immutable in many languages (Java, Python, JavaScript)
Special operations like concatenation, substring, etc.
Often have built-in methods for common operations

Common String Operations

Operation	Time Complexity	Description
Length	O(1)	Getting the length of a string
Concatenation	O(n+m)	Joining two strings
Substring	O(k)	Extracting a portion of the string
String Comparison	O(n)	Comparing two strings

Array Implementation

Java Implementation

// Declaring and initializing arrays in Java
// Fixed-size array
int[] fixedArray = new int[5];  // Creates an array of size 5 with default values (0)

// Initialize with values
int[] initializedArray = {1, 2, 3, 4, 5};  // Creates and initializes an array

// Accessing elements
int thirdElement = initializedArray[2];  // Arrays are 0-indexed, so this gets the 3rd element (value 3)

// Modifying elements
initializedArray[1] = 10;  // Changes the second element to 10

// Array length
int length = initializedArray.length;  // Gets the length of the array

// Dynamic arrays using ArrayList
import java.util.ArrayList;

ArrayList<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(1);  // Adds element to the end
dynamicArray.add(2);
dynamicArray.add(3);

dynamicArray.get(1);  // Gets element at index 1 (value 2)
dynamicArray.set(1, 10);  // Sets element at index 1 to 10
dynamicArray.remove(0);  // Removes element at index 0
dynamicArray.size();  // Gets the size of the ArrayList

Python Implementation

# Declaring and initializing arrays (lists) in Python
# Python lists are dynamic by default
my_list = [1, 2, 3, 4, 5]  # Creates and initializes a list

# Accessing elements
third_element = my_list[2]  # Lists are 0-indexed, so this gets the 3rd element (value 3)

# Modifying elements
my_list[1] = 10  # Changes the second element to 10

# List length
length = len(my_list)  # Gets the length of the list

# Common list operations
my_list.append(6)  # Adds element to the end
my_list.insert(1, 7)  # Inserts 7 at index 1
my_list.pop()  # Removes and returns the last element
my_list.pop(0)  # Removes and returns element at index 0
my_list.remove(3)  # Removes the first occurrence of value 3

# List slicing
sub_list = my_list[1:4]  # Gets elements from index 1 to 3
reversed_list = my_list[::-1]  # Reverses the list

# List comprehension
squares = [x**2 for x in range(10)]  # Creates a list of squares from 0 to 9

String Implementation

Java Implementation

// String operations in Java
String str = "Hello, World!";

// String length
int length = str.length();  // Returns 13

// Accessing characters
char firstChar = str.charAt(0);  // Returns 'H'

// Substring
String sub = str.substring(0, 5);  // Returns "Hello"

// String concatenation
String newStr = str + " How are you?";  // Using + operator
String anotherStr = str.concat(" How are you?");  // Using concat method

// String comparison
boolean isEqual = str.equals("Hello, World!");  // Returns true
boolean isEqualIgnoreCase = str.equalsIgnoreCase("hello, world!");  // Returns true

// String searching
int index = str.indexOf("World");  // Returns 7
boolean contains = str.contains("Hello");  // Returns true

// String modification (creates new strings as Strings are immutable in Java)
String replaced = str.replace("Hello", "Hi");  // Returns "Hi, World!"
String upperCase = str.toUpperCase();  // Returns "HELLO, WORLD!"
String lowerCase = str.toLowerCase();  // Returns "hello, world!"
String trimmed = "  Hello  ".trim();  // Returns "Hello"

// Splitting strings
String[] parts = "apple,banana,orange".split(",");  // Returns ["apple", "banana", "orange"]

// StringBuilder for efficient string manipulation
StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(", ");
sb.append("World!");
String result = sb.toString();  // Returns "Hello, World!"

Python Implementation

# String operations in Python
s = "Hello, World!"

# String length
length = len(s)  # Returns 13

# Accessing characters
first_char = s[0]  # Returns 'H'

# Substring (slicing)
sub = s[0:5]  # Returns "Hello"

# String concatenation
new_str = s + " How are you?"  # Using + operator

# String comparison
is_equal = (s == "Hello, World!")  # Returns True
is_equal_ignore_case = (s.lower() == "hello, world!")  # Returns True

# String searching
index = s.find("World")  # Returns 7
contains = "Hello" in s  # Returns True

# String modification (creates new strings as Strings are immutable in Python)
replaced = s.replace("Hello", "Hi")  # Returns "Hi, World!"
upper_case = s.upper()  # Returns "HELLO, WORLD!"
lower_case = s.lower()  # Returns "hello, world!"
trimmed = "  Hello  ".strip()  # Returns "Hello"

# Splitting strings
parts = "apple,banana,orange".split(",")  # Returns ["apple", "banana", "orange"]

# Join strings
joined = ", ".join(["apple", "banana", "orange"])  # Returns "apple, banana, orange"

# String formatting
formatted = f"The answer is {42}"  # Returns "The answer is 42"
formatted_old = "The answer is {}".format(42)  # Returns "The answer is 42"

Common Array & String Patterns

1. Two Pointers Technique

Using two pointers to solve array problems efficiently, often reducing the time complexity from O(n²) to O(n).

// Java implementation of Two Sum using two pointers
// (array must be sorted for this approach)
public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target) {
            return new int[] {left + 1, right + 1}; // 1-indexed result
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return new int[] {-1, -1}; // No solution found
}

2. Sliding Window

Using a window that slides through an array to efficiently process subarrays or substrings.

# Python implementation of Maximum Sum Subarray of size K
def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
    
    # Compute sum of first window of size k
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window from left to right
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

3. Frequency Counter

Using a hash map to count occurrences of elements, useful for problems involving anagrams, duplicates, etc.

// Java implementation of Valid Anagram
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    int[] counter = new int[26]; // Assuming lowercase English letters
    
    // Count characters in s
    for (char c : s.toCharArray()) {
        counter[c - 'a']++;
    }
    
    // Decrement counts for characters in t
    for (char c : t.toCharArray()) {
        counter[c - 'a']--;
        // If character appears more times in t than in s
        if (counter[c - 'a'] < 0) {
            return false;
        }
    }
    
    return true;
}

Practice Problems

Apply your knowledge of arrays and strings by solving these carefully selected problems:

1. Two Sum

Given an array of integers and a target sum, return indices of the two numbers that add up to the target.

EasyHash TableTwo Pointers

2. Valid Palindrome

Determine if a string is a palindrome, considering only alphanumeric characters and ignoring case.

EasyTwo PointersString

3. Maximum Subarray

Find the contiguous subarray with the largest sum.

MediumDynamic ProgrammingKadane's Algorithm

4. Longest Substring Without Repeating Characters

Find the length of the longest substring without repeating characters.

MediumHash TableSliding Window

Module Contents

Learning Resources

Back to Foundations Next: Linked Lists