Module 2: Arrays & Strings

Arrays and Strings are the backbone of Data Structures and Competitive Programming. Almost 70–80% of interview and CP problems are built directly or indirectly on these concepts. Mastery here decides how fast and accurately a learner can solve real problems.

ARRAYS

What is an Array?

An array is a collection of elements of the same data type stored in contiguous memory locations.
Arrays allow constant-time access using index, which makes them extremely powerful.

Example:

int[] arr = {10, 20, 30, 40};

Accessing arr[2] takes O(1) time.

One-Dimensional Arrays

A one-dimensional array is a linear structure where elements are stored in a single line.

Common operations:

• Traversal
• Searching
• Updating values
• Finding min/max
• Prefix calculations

Example: Find sum of array

int sum = 0;
for(int i = 0; i < n; i++){
    sum += arr[i];
}

Time Complexity: O(n)
Space Complexity: O(1)

Two-Dimensional Arrays (Matrices)

A 2D array is an array of arrays, commonly used to represent matrices, grids, and tables.

Example:

int[][] matrix = new int[3][3];

Traversal:

for(int i = 0; i < rows; i++){
    for(int j = 0; j < cols; j++){
        System.out.print(matrix[i][j] + " ");
    }
}

Applications:

• Image processing
• Game boards
• Graph problems
• Dynamic programming tables

Dynamic Arrays Concept

Dynamic arrays grow or shrink automatically when needed.

Examples:

• Java: ArrayList
• C++: vector
• Python: list

Example:

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);

Internally:

• When capacity is full, a new larger array is created
• Old elements are copied
• Time complexity of add(): Amortized O(1)

Sliding Window Technique

Sliding window is used when dealing with subarrays or substrings of fixed or variable size.

Instead of recalculating values repeatedly, we slide the window.

Example: Maximum sum of subarray of size k

int sum = 0;
for(int i = 0; i < k; i++){
    sum += arr[i];
}

int maxSum = sum;

for(int i = k; i < n; i++){
    sum = sum + arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, sum);
}

Time Complexity: O(n)
Without sliding window: O(n²)

Prefix Sum Technique

Prefix sum helps answer range queries efficiently.

Prefix array:

prefix[0] = arr[0];
for(int i = 1; i < n; i++){
    prefix[i] = prefix[i - 1] + arr[i];
}

Range sum from L to R:

sum = prefix[R] - prefix[L - 1];

Used in:

• Range queries
• Subarray problems
• Optimization problems

Kadane’s Algorithm

Kadane’s Algorithm finds the maximum subarray sum in O(n).

Idea:

• Either extend the previous subarray
• Or start a new subarray

Example:

int maxSum = arr[0];
int currentSum = arr[0];

for(int i = 1; i < n; i++){
    currentSum = Math.max(arr[i], currentSum + arr[i]);
    maxSum = Math.max(maxSum, currentSum);
}

Time Complexity: O(n)
This is one of the most asked interview algorithms.

Two-Pointer Approach

Two pointers reduce complexity by processing elements from both ends or in a controlled manner.

Example: Check if array is sorted

int i = 0, j = n - 1;
while(i < j){
    if(arr[i] > arr[j]){
        return false;
    }
    i++;
    j--;
}

Used in:

• Pair sum problems
• Palindromes
• Sorted arrays
• Partitioning problems

Difference Array Technique

Difference arrays allow efficient range updates.

Instead of updating each element:

diff[l] += val;
diff[r + 1] -= val;

After all updates:

arr[0] = diff[0];
for(int i = 1; i < n; i++){
    arr[i] = arr[i - 1] + diff[i];
}

Used in:

• Range increment problems
• Optimization under constraints

Matrix Traversal Patterns

Common traversal patterns:

• Row-wise
• Column-wise
• Spiral traversal
• Diagonal traversal
• Zig-zag traversal

Example: Spiral traversal (conceptual)

• Move right
• Move down
• Move left
• Move up
• Shrink boundaries

These patterns appear frequently in interviews.

Subarrays vs Subsequences

Subarray:

• Continuous
• Example: {2, 3, 4} from {1, 2, 3, 4}

Subsequence:

• Not necessarily continuous
• Example: {1, 3, 4}

Important facts:

• Number of subarrays = n(n+1)/2
• Number of subsequences = 2ⁿ

STRINGS

String Basics & Memory

A string is a sequence of characters.

Java strings are:

• Immutable
• Stored in string pool

Example:

String s = "hello";

Any modification creates a new string, not changes the old one.

Character Frequency Problems

These problems count occurrences of characters.

Example:

int[] freq = new int[26];
for(char c : s.toCharArray()){
    freq[c - 'a']++;
}

Used in:

• Anagrams
• Frequency sorting
• Valid strings

Palindrome Problems

A palindrome reads the same forwards and backwards.

Two-pointer approach:

int l = 0, r = s.length() - 1;
while(l < r){
    if(s.charAt(l) != s.charAt(r)){
        return false;
    }
    l++;
    r--;
}

Used in:

• String validation
• Substring problems
• Interview questions

Anagram Problems

Two strings are anagrams if they have the same character frequency.

Approach:

• Count frequency of both strings
• Compare arrays

Time Complexity: O(n)

---

Pattern Matching

Pattern matching finds occurrences of a pattern in a string.

Basic approach:

• Brute force: O(n × m)

Advanced algorithms (later modules):

• KMP
• Rabin-Karp
• Z Algorithm

---

String Compression

Compress repeated characters.

Example:

aaabbc → a3b2c1

Implementation uses:

• Loop
• Counter
• StringBuilder

---

Substrings & Rotations

Substring:

• Continuous part of string

Rotation:

• String B is rotation of A if B is substring of A+A

Example:

String s = "abcde";
String t = "cdeab";

boolean isRotation = (s + s).contains(t);

---

Longest Common Prefix

Find common prefix among multiple strings.

Example:

String prefix = strs[0];
for(int i = 1; i < strs.length; i++){
    while(!strs[i].startsWith(prefix)){
        prefix = prefix.substring(0, prefix.length() - 1);
    }
}

---

String Hashing (Introduction)

String hashing converts strings into numbers for fast comparison.

Used in:

• Pattern matching
• Avoiding direct string comparison
• Competitive programming

Concept:

hash = (hash * base + char) % mod;

Advanced usage covered in later modules.