Chapter 10 — Arrays, Strings

Concept and purpose

An array stores a collection of items of the same type under a single variable name. Instead of declaring separate variables for similar data, arrays let you group them and work with them using indexes. Typical uses include storing student marks, daily temperatures, or elements of a mathematical vector. Thinking of an array as a list of boxes helps visualise operations.

Memory organisation and contiguous storage

Arrays allocate a block of contiguous memory large enough to hold all elements. If each element requires s bytes and the array has n elements, the total block size is n×s bytes. The first element A[0] is at the base address. The element A[i] is found at base_address + i×s. This predictable layout enables direct computation of memory addresses and allows random access to any element in constant time by index.

Indexing conventions and bounds checking

Most modern programming languages use zero-based indexing, meaning indices range from 0 to n-1 for an array of size n. It is crucial to observe these bounds. Accessing A[n] or A[-1] is invalid and leads to runtime errors or undefined behaviour. In exams and programming tasks always state whether indices are 0-based or 1-based and check boundary conditions explicitly to avoid off-by-one mistakes.

Declaration, initialisation and logical vs physical size

Declaration reserves memory for a given number of elements: for example, declaring an integer array of size 10 reserves space for 10 integers. Initialisation can be immediate, with values provided at declaration, or deferred by filling elements later. Keep two ideas separate: physical capacity (how many slots are allocated) and logical size (how many slots currently hold valid data). When inserting or deleting, update logical size rather than reallocating each time unless necessary.

Practical benefits and limitations

Advantages include constant-time access to any index and simple, compact representation. Limitations are fixed size in low-level languages and expensive insertions/deletions in the middle due to required shifting of elements. Choosing arrays is sensible when you need fast random access and memory for all elements fits comfortably. Understanding memory layout equips students to reason about time and space trade-offs for algorithms that use arrays.

Traversal basics

Traversal is visiting each element of an array, usually in order. The most common pattern is a for-loop that runs from the first valid index to the last valid index. Traversal is used to print elements, compute aggregates such as sum or average, find minimum or maximum, and apply transformations to each element. Time complexity for a full traversal is O(n), where n is the number of elements visited.

Insertion details

To insert a new value at index k (0 ≤ k ≤ size), make sure there is space. If the array has free capacity, shift existing elements from the last valid index down to k one position to the right to avoid overwriting data. Then store the new value at A[k] and increase logical size by one. If the array is full, you must either reject the insertion or allocate a larger array and copy elements. Inserting at the end (append) avoids shifting and costs O(1) if capacity exists; inserting near front costs O(n) in the worst case.

Deletion process

To delete an element at index k (0 ≤ k < size), move elements from k+1 to last index one position to the left to fill the gap, then decrease logical size. If deletion is frequent and order does not matter, an alternative O(1) technique is to swap the last element into position k and reduce size, but this disturbs element order—useful in some applications but not when order must be preserved.

Updating and direct access

Direct access by index is a key strength: reading or assigning A[i] requires constant time O(1). Use this for value updates and replacements. When performing multiple updates, prefer direct indexed assignment rather than searches where possible.

Careful shifting and loop direction

When shifting elements right for insertion, iterate from the end towards k to avoid overwriting. For shifting left during deletion, iterate from k to end-1. Always update the logical size and check bounds before accessing indices. Remember to test edge cases like empty arrays, single-element arrays, insertion at index 0 and insertion at index equal to current size (append).

What is a two-dimensional array?

A two-dimensional array is an array in which each element is itself an array. Think of it as a grid or table with rows and columns. A typical notation is A[r][c] for a matrix with r rows and c columns. Each element is identified by two indices: the row index and the column index. Two-dimensional arrays are used to represent tables, images (pixels), chess boards, and matrices in mathematics.

Memory layout and row-major order

In many languages, 2D arrays are stored in row-major order: the entire first row is stored contiguously, followed by the entire second row, and so on. Knowing the storage order matters for performance: iterating row by row accesses contiguous memory and is usually faster due to cache friendliness. Column-wise access, which jumps between rows for the same column, can be slower because it reads non-contiguous memory locations.

Declaration and initialisation

Declare by specifying both dimensions or by providing initial values. Example: create a 3×4 integer matrix with 3 rows and 4 columns. Initialisation can fill all entries with zero or specific numbers. When reading input into a matrix, use nested loops: an outer loop for rows and an inner loop for columns to assign each A[i][j].

Traversing a matrix

Traversal uses nested loops: for i from 0 to r-1 and for j from 0 to c-1, process A[i][j]. This visits every element once, costing O(r×c) time. For certain operations, other traversal orders (diagonals, spiral) may be needed; adapt loops accordingly and always check index bounds.

Common matrix operations

Addition and subtraction require equal dimensions and are performed element-wise. Transpose swaps rows and columns: the transpose T of A has T[i][j] = A[j][i]. For square matrices transpose can be done in-place by swapping elements A[i][j] with A[j][i] for i

Sparse matrices and efficiency

If most entries are zero, storing all entries wastes memory. Sparse representations list only non-zero entries with their coordinates. For ICSE problems, full arrays are typical, but be aware of sparse representations for large-scale problems. Always check matrix dimensions and handle mismatched sizes gracefully in code and written solutions.

Linear search explained

Linear search inspects each element from start to end until the target is found. It makes no assumption about order and is therefore simple and generally applicable. In the best case the target is at the first position (O(1)); in the worst case the target is absent or at the last position which requires visiting all n elements, giving O(n) time. Linear search is ideal for small arrays or when the cost of maintaining sorted order outweighs search benefits.

Binary search in detail

Binary search requires the array to be sorted. It begins by comparing the target to the middle element. If equal, we are done. If the target is smaller, we repeat on the left subarray; if larger, on the right subarray. Each comparison halves the search interval, so after k steps the interval size is about n/2^k. This leads to logarithmic time O(log n). Binary search can be implemented iteratively (using low and high pointers) or recursively. Careful handling of mid calculation (e.g., mid = low + (high - low)/2) avoids overflow in some languages, and choosing how to update low/high correctly avoids infinite loops.

Edge cases and duplicates

Test binary search on arrays with zero, one and two elements to ensure correctness. When duplicates exist and you must find the first or last occurrence, modify the algorithm: after finding a match, continue searching left for the first occurrence or right for the last, adjusting pointers accordingly. Off-by-one errors are common—draw index ranges and simulate steps to verify updating rules.

Choosing the right search

If multiple searches will be performed on the same dataset and the dataset is static, sorting once and using binary search repeatedly is often efficient. If the dataset changes frequently with many insertions or deletions, the cost of keeping it sorted may outweigh binary search benefits. For very small lists, linear search might be faster due to low overhead. Always reason about the number of searches m and array size n: compare O(n m) for repeated linear searches with O(n log n + m log n) for sorting plus binary searches to pick the best approach.

Practical tips

Implement and test both searches for different inputs. Use assertions for preconditions such as sorted input for binary search. Demonstrate understanding of trade-offs in written exam answers and include a small dry-run to show correctness.

Why sorting matters

Sorting orders data to simplify other operations like searching, merging and presentation. It often improves the performance of repeated queries and enables algorithms that assume sorted input. Understanding basic sorting algorithms teaches about comparisons, swaps, and algorithmic cost.

Bubble sort mechanics

Bubble sort repeatedly steps through the array, comparing adjacent items and swapping them when they are in the wrong order. After the first pass the largest element reaches the end; after the second pass the second-largest is placed correctly, and so on. Bubble sort is simple and stable but inefficient for large n, with worst-case time O(n^2). An optimisation stops early if a pass makes no swaps, indicating the array is already sorted.

Selection sort explained

Selection sort divides the array into a sorted prefix and unsorted suffix. Repeatedly select the smallest element from the unsorted part and swap it with the first element of the unsorted part, extending the sorted prefix by one. Selection sort always performs O(n^2) comparisons but only O(n) swaps, which can be advantageous when swaps are expensive. It is not stable by default unless implemented with care.

Insertion sort and its strengths

Insertion sort builds a sorted portion at the front by taking the next element from the unsorted portion and inserting it into the correct place within the sorted portion. This involves shifting larger elements to the right to make space and then placing the current element. Insertion sort is O(n^2) in the worst case but O(n) in the best case when input is already nearly sorted. It is stable and efficient for small or nearly-sorted datasets and is often used within more complex sorting algorithms for small subarrays.

Choosing a simple sort

For classroom and small data choose insertion sort when data is almost sorted, selection sort when swaps are costly, and bubble sort mainly for demonstration and very small inputs. Always include a note on time complexity and stability in exam answers, and illustrate operations using small arrays to show understanding of the algorithm step-by-step.

When combining makes sense

Sorting a dataset before performing many searches is sensible when the cost of sorting is outweighed by faster queries afterward. Sorting once may be expensive, but if you will run many searches, each search can be much faster on sorted data using binary search. The decision depends on the sizes involved and the number of queries.

Cost comparison and reasoning

Assume sorting uses an efficient O(n log n) method (or a built-in sort). Then m binary searches cost O(m log n) after the initial sort, giving total O(n log n + m log n). If instead each search uses linear scan, total cost is O(m n). Compare these: if m is large, sorting first is beneficial. For example, with n = 10000 and m = 1000, sorting once and binary searching is typically far faster than 1000 linear scans. Conversely, for small n or very few queries, sorting overhead may not pay off.

Practical constraints

If the dataset changes often (many insertions or deletions), keeping it sorted may be costly because each change could require shifting elements or re-sorting. In such dynamic situations, consider data structures that support efficient dynamic operations (e.g., balanced trees) in more advanced study. For ICSE-level problems, explicitly reason about whether data is static or dynamic before suggesting sorting.

Implementation notes and pitfalls

When sorting prior to searches, remember that sorting changes element order. If output requires original positions, preserve indices using pairs (value, original_index) or maintain a parallel index array. Also consider stability: stable sorts preserve relative order of equal elements which matters in some applications. When duplicates exist and you need first/last occurrence, use binary search variants adapted for such requirements.

Example scenarios

Examples: handling many membership queries against a fixed database, ranking students and answering position queries, and merging sorted logs from multiple sources. In exam answers show both the computational comparison and a small example demonstrating the approach step-by-step.

What is a string?

A string is a sequence of characters used to represent text such as names, messages or codes. Conceptually, a string is like an array where each position holds a character. Common operations include reading characters by index, joining strings, comparing them, slicing substrings and searching within them. Strings are central to input/output and text processing tasks.

Internal representation

Strings are often stored as arrays of characters. Some languages store a terminating character (e.g., a null character) to mark the end, while others store the length explicitly. This affects how functions like length, concatenation and slicing are implemented under the hood. For classroom problems assume a simple representation where characters occupy one slot each and indexing is 0-based, unless the question states otherwise.

Basic operations and semantics

Key operations include concatenation (joining two strings), comparison (lexicographic order or equality), substring extraction (slicing a portion of a string), and character access by index. Many standard libraries provide built-in functions to perform these tasks; however, understanding the underlying array-like behaviour is important for reasoning about complexity and correctness.

Indexing rules and edge cases

Valid indices are 0..n-1 for a string of length n. Accessing s[0] requires checking that n > 0. When slicing, be clear whether the end index is inclusive or exclusive and handle empty substrings. For problems involving characters, be explicit about case sensitivity and whether to ignore punctuation or whitespace.

Practical usage and examples

Strings are used to store names, sentences and codes. Parsing tasks break strings into tokens; searching tasks locate substrings; formatting tasks build output lines. For ICSE problems practice reading input lines, trimming spaces, tokenising and converting numeric tokens to integers. Show sample inputs and outputs in exam answers to clarify your approach.

Concatenation mechanics

Concatenation joins two strings end-to-end. If s has length m and t has length n, the concatenated string s+t has length m+n. If strings are implemented as immutable objects, concatenation typically allocates a new string and copies characters from s and t into it; this costs O(m+n) time. When concatenating many strings in a loop, repeated copying leads to poor performance, so efficient builders or join operations are preferred.

Lexicographic comparison

Comparing strings is done character by character from the start. At the first differing character, the order of their unicode or ASCII codes decides which string is smaller. If one string is a prefix of the other, the shorter string is smaller. Comparisons are case-sensitive by default; convert both strings to a common case for case-insensitive comparisons.

Substring and slicing

Extracting a substring copies a contiguous block of characters from the original string. For indices i (start) and j (end exclusive), the substring contains characters s[i..j-1] and length j-i. Slicing is commonly used to extract prefixes, suffixes, file extensions, or tokens between delimiters. Always validate indices so they lie within 0..n and handle empty substrings when i == j.

Performance considerations

Concatenation cost is proportional to the total length of strings involved. Frequent concatenation can create many temporary strings and increase both time and memory usage. Use collections to gather parts and then perform a single join, or use a mutable string builder if available. For comparisons, worst-case cost is O(min(m,n)). For substring operations, copying costs O(length_of_substring).

Practical examples and pitfalls

To get file extension for 'report.pdf', find the last '.' then slice the substring after it. Beware of filenames with no dot. When comparing names for sorting, decide and state whether case should affect order. Demonstrate steps on examples when writing answers in exams.

Searching for a character

Searching for a single character in a string is done by scanning characters sequentially from the start until the character is found or the end of the string is reached. This linear scan requires O(n) time for a string of length n. Many languages provide built-in functions to return the index of first or last occurrence; internally they perform similar linear checks.

Naive substring search explained

The naive substring search attempts to match the pattern at each possible starting position in the text. For a text of length n and a pattern of length m, there are n-m+1 possible starting positions. At each starting position the algorithm compares up to m characters, so the worst-case time is O(n×m). The naive method is easy to write and understand, making it suitable for classroom and small inputs.

Handling overlaps and worst cases

Overlapping patterns (for example pattern 'aa' in text 'aaaa') create many matches and can trigger worst-case behaviour. The naive approach advances the starting position by one after a mismatch or after recording a match, which handles overlaps correctly. For pathological inputs the naive algorithm may perform many repeated comparisons; understanding this helps motivate advanced algorithms later.

Practical tips

Always check for trivial cases: an empty pattern typically matches at index 0; if pattern length exceeds text length there is no match. Stop matching early at a start position when remaining text length is less than pattern length. For exam answers, dry-run the algorithm on a short example to show how indices move and how matches are reported.

When to learn advanced methods

Advanced pattern matching algorithms such as Knuth-Morris-Pratt (KMP) and Rabin-Karp improve worst-case or expected performance but are more complex. For Class 11 the naive approach suffices; however, be aware of its limitations and that better methods exist for large-scale text processing.

Character encoding basics

Characters are represented inside a computer by numeric codes. ASCII assigns codes to common English characters in the range 0–127. Unicode is a larger standard that covers many scripts and symbols; UTF-8 is a popular encoding that represents Unicode characters using one to four bytes. For many classroom problems assume simple single-byte characters; for multi-language input be aware that characters may occupy multiple bytes.

Why encoding matters for string operations

If characters are multibyte, functions that index by byte may not correspond to logical characters. For example, slicing at a byte boundary may break a multibyte character. High-level languages provide character-aware functions and libraries that hide these details; when working close to bytes, understand the encoding used.

Parsing and tokenisation

Parsing splits text into meaningful parts called tokens using delimiters (spaces, commas, tabs) or fixed widths. Tokenisation can be implemented by scanning characters and collecting characters into a token until a delimiter is found, then storing the token and continuing. Many languages offer split functions to perform this quickly, but manual implementations help understand edge cases like multiple consecutive delimiters and leading/trailing whitespace.

Common parsing tasks and tips

Examples: reading CSV lines like '12,Peter,85' requires splitting by ',' and converting numeric tokens to integers. Extracting a username from 'user@example.com' requires finding '@' and slicing before it. Always trim tokens to remove extra whitespace and validate that numeric tokens contain only digits (and optional sign). Handle missing fields by returning an error or default values as required.

Testing and robustness

Test parsing with inputs that include extra spaces, empty tokens (consecutive delimiters), and invalid numeric fields. For ICSE answers, describe how you will handle malformed input and provide example inputs and outputs. For larger systems, consider library functions that handle locale and encoding, but for exam-level problems a clear manual approach usually suffices.

Mutable strings

Mutable strings can be changed in place: characters can be replaced, appended or removed without creating a new object each time. Languages that offer mutable character arrays or string-builder types allow efficient in-place modifications. This is useful when building large strings incrementally, because append operations do not necessarily copy the entire content every time.

Immutable strings

Immutable strings cannot be changed after creation. Any operation that appears to modify a string returns a new string. Immutability simplifies reasoning about programs because shared references cannot change unexpectedly. Many high-level languages treat strings as immutable for safety and simplicity. However, repeated concatenation with immutable strings can be very inefficient because each concatenation typically allocates new memory and copies existing characters.

Performance implications

Consider concatenating n strings of average length L in a loop: naive concatenation with immutable strings can lead to O(n^2 × L) total copying in the worst case. An efficient alternative is to collect parts in a mutable buffer (string builder) or a list and then join them once; this reduces copying and can achieve O(total_length) time overall. When space is limited, avoid creating many temporary strings.

Correctness and safety

Immutability prevents side effects and makes functions safer to use with shared data. Mutable strings permit in-place edits but require care to avoid accidental changes when a string is shared. When writing exam answers, state assumptions about mutability and choose an approach that balances clarity and efficiency for the given problem.

Practical classroom advice

When asked to build a large string in code, mention using a string builder or joining a list. When asked to modify individual characters, specify use of a mutable character array if the language's string is immutable. Provide simple examples showing both approaches and explain the efficiency difference briefly.

Recognising common patterns

Many array and string problems reuse a small set of patterns. Identifying these patterns quickly helps design correct solutions during exams. Frequent patterns include reversing, checking for palindromes, counting frequencies using auxiliary arrays, using two-pointer techniques for pair problems, and sliding-window methods for subarray or substring problems.

Reverse and palindrome

Reversing an array or string in-place swaps symmetric elements: for i from 0 to floor((n-1)/2) swap A[i] with A[n-1-i]. This uses O(1) extra space and O(n) time. For palindrome check, use two indices i and j starting at ends and compare A[i] and A[j] while moving i forward and j backward. Stop early on mismatch. These patterns are simple yet common in exam questions.

Frequency counting

When elements belong to a small known range (digits 0–9 or lowercase letters), frequency arrays are effective. Initialise a count array of appropriate size and increment counts while scanning. This gives O(n + range) time and is straightforward to implement for tasks like counting occurrences or finding the most frequent element.

Two-pointer methods and optimisations

Two-pointer techniques often turn quadratic solutions into linear ones. Examples: find pairs with a given sum in a sorted array by placing one pointer at start and one at end and moving them based on pair sum; remove duplicates in-place by maintaining a write pointer; partition arrays by pivot using pointer swaps. These methods rely on careful pointer movement and boundary checks.

Practice advice

Solve many small problems applying these patterns and dry-run them on sample inputs. Write helper functions for repeated tasks and always test boundary cases (empty inputs, single-element inputs, duplicates). In written answers, explain your chosen pattern and show a short example to demonstrate correctness.

Space considerations and memory layout

Arrays require contiguous memory blocks. A 2D array of r rows and c columns requires r×c storage locations, which can be large. Strings stored as arrays of characters take space proportional to length. When allocating fixed-size arrays, keep in mind physical capacity versus logical size to avoid wasting memory or causing overflow. In constrained environments avoid large temporary copies of arrays or strings.

Time complexity review

Understand common costs: access or update by index is O(1); full traversal of n elements is O(n); insertion or deletion in the middle is O(n) due to shifting; naive substring search costs O(n×m) for text of length n and pattern of length m; simple sorting methods cost O(n^2), while efficient sorts are O(n log n). Knowing these costs helps choose appropriate algorithms for given input sizes.

Testing and edge cases

Always test your functions with minimal inputs (empty, single element), typical inputs and large inputs near expected limits. Check boundary conditions such as index 0 and index n-1, and handle absence of search targets gracefully. For string parsing, test multiple delimiters, leading/trailing whitespace and malformed tokens. Use assertions or conditional checks in code to ensure preconditions hold before operations like indexing.

Trade-offs and practical choices

Balance memory and time: if memory is plentiful, copying data can simplify logic; if memory is tight, prefer in-place operations even if slightly more complex. For repeated operations (many searches), pay up-front cost to sort if it reduces total time. For small input sizes, prefer clarity and simplicity over micro-optimisation.

Debugging and verification

Use trace prints, small test cases and helper functions to isolate errors. Include dry-run examples in written solutions to show step-by-step operation. When discussing algorithm choices in exams, justify them with complexity analysis and mention expected behaviour on edge cases.

Off-by-one errors

Off-by-one mistakes happen when loop bounds are incorrect. Decide whether to use < or ≤. For 0-based arrays, a loop from i = 0 to i < n is usually correct. A loop using i <= n will try to access A[n] and cause an error. Always test with empty arrays and single-element arrays to catch such mistakes early. When slicing strings, be explicit about whether the end index is inclusive or exclusive.

Uninitialised values and logical size

Always initialise arrays before using them. Keep separate variables for allocated capacity and the current number of valid elements. Do not assume unassigned slots are zero. When deleting elements, update the logical size; when inserting, ensure you do not exceed capacity without reallocating.

Boundary handling in 2D arrays and strings

Nested loops must handle both row and column bounds. For matrices check row and column dimensions before operations like addition or multiplication. For strings, verify that length > 0 before accessing s[0] and check indices when extracting substrings. Use guard conditions to prevent invalid access.

Mutability and assumptions

Know whether your language treats strings as mutable. Attempting in-place edits on immutable strings will fail. If many modifications are necessary, use mutable buffers or character arrays. Mention these assumptions when writing answers to show awareness of language-specific behaviour.

Debugging strategies and good practices

Use print statements to display indices, loop counters and intermediate values. Test helper functions separately. Add comments and use meaningful variable names to make code understandable. When stuck, reduce the input size and trace execution step by step. In written exams include a dry-run on a small example to demonstrate correctness and help find logical faults.

Program design steps

Begin by reading the problem carefully and identifying the input format and required output. Decide the appropriate data structures: an array for a fixed collection of numbers, a 2D array for matrices or grids, or a string for textual input. Plan the steps: read input, parse if necessary, process using helper functions (search, sort, parse), and output results in the requested format.

Modularity and testing

Divide the program into small functions: e.g., readArray, printArray, findMax, sortArray, tokenizeString. Test each function independently with simple inputs before integrating. For sorting and searching tasks, test edge cases like empty inputs, duplicates, and maximum sizes. Clear variable names and comments are helpful for both debugging and exam marking.

Example problem types

ICSE-style tasks include computing sums and averages from arrays, sorting names and printing them alphabetically, checking palindromes, counting vowels and consonants, parsing CSV-style input, and manipulating matrices for transpose or multiplication. For each problem, state assumptions and handle malformed input gracefully, either by reporting an error or using default behaviour as required by the question.

Exam presentation and marks

In written answers explain the approach briefly, present the algorithm with loop details and invariants, and perform a dry-run on a small example showing key steps and indices. In coding tasks prefer clarity and correctness; if asked, discuss complexity and possible optimisations. Use library functions where allowed but mention their complexity if the question asks for analysis.

Practice and improvement

Regular practice on varied problems builds confidence. Time your solutions when practising to develop speed under exam conditions. Review common pitfalls such as off-by-one errors and uninitialised variables, and incorporate debugging checks in your code. Clear thinking and careful testing lead to correct and well-received answers.