T TestsWorld
← All topic guides

Arrays & strings: formulas, shortcuts & solved examples

What it is

An array stores elements of the same type in contiguous memory, so any index can be reached in O(1). A string is essentially an array of characters, though in Java and Python strings are immutable. Arrays and strings dominate the first coding question in most placement tests, so a handful of patterns solve a large share of problems.

Key rules

Indexing and memory

  • Address of A[i] = Base address + i × (size of one element), for 0-based arrays.
  • For a 2D row-major array with C columns: address of A[i][j] = Base + (i × C + j) × size.
  • Negative indices in Python count from the end: a[-1] is the last element.

Operation costs

Operation Array Dynamic array (list)
Access by index O(1) O(1)
Search unsorted O(n) O(n)
Insert/delete at end n/a O(1) amortised
Insert/delete at start O(n) O(n)

Core patterns

  • Prefix sum: P[i] = A[0] + ... + A[i]. Sum of A[l..r] = P[r] − P[l − 1] in O(1).
  • Two pointers: one at each end of a sorted array, move inward based on comparison.
  • Sliding window: maintain a running sum or count over a window, add the entering element, remove the leaving one.
  • Kadane's algorithm: cur = max(x, cur + x); best = max(best, cur) gives the maximum subarray sum in O(n).
  • Frequency count: a 26-slot array or a hash map for characters.

Shortcuts

  1. Rotation by slicing. Left-rotating by k equals a[k:] + a[:k]; in-place, reverse the first k, reverse the rest, then reverse the whole array.
  2. Palindrome check. Compare s[i] with s[n − 1 − i] for i < n/2, or in Python simply s == s[::-1].
  3. Anagram check. Two strings are anagrams if their character counts match; sorting both is O(n log n), counting is O(n).

Solved examples

Example 1: Prefix sums

a = [3, 1, 4, 1, 5, 9, 2, 6]
p = []
running = 0
for x in a:
    running += x
    p.append(running)
print(p)
print(p[5] - p[1])

Solution. Running totals: 3, 4, 8, 9, 14, 23, 25, 31. The second line asks for the sum of a[2..5] = 4 + 1 + 5 + 9 = 19, and indeed P[5] − P[1] = 23 − 4 = 19.

Output:

[3, 4, 8, 9, 14, 23, 25, 31]
19

Example 2: Kadane's maximum subarray

b = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
cur = best = b[0]
for x in b[1:]:
    cur = max(x, cur + x)
    best = max(best, cur)
print(best)

Solution. cur goes −2, 1, −2, 4, 3, 5, 6, 1, 5 and best ends at 6, from the subarray [4, −1, 2, 1]. Think of it as a trader's best run of daily profit and loss: once the running total goes negative, start fresh.

Example 3: Rotation

x = [1, 2, 3, 4, 5]
k = 2
print(x[k:] + x[:k])

Solution. x[2:] is [3, 4, 5] and x[:2] is [1, 2]. Output [3, 4, 5, 1, 2], a left rotation by 2. For k larger than n, use k % n first.

Example 4: Most frequent character

from collections import Counter
s = "bengaluru"
print(Counter(s).most_common(1))
print(s == s[::-1], "malayalam" == "malayalam"[::-1])

Solution. Counts: b 1, e 1, n 1, g 1, a 1, l 1, u 2, r 1. The most common is ('u', 2). "bengaluru" reversed is "urulagneb", so it is not a palindrome (False), while "malayalam" reads the same both ways (True).

Output:

[('u', 2)]
False True

Common mistakes

  1. Off-by-one in prefix sums. Sum of A[l..r] uses P[l − 1], and when l = 0 you need P[−1] = 0; many people pad P with a leading zero to avoid this.
  2. Modifying a list while iterating over it. Removing elements during a for loop skips items; build a new list instead.
  3. Concatenating strings in a loop. In Java and Python this can become O(n²); use a StringBuilder or "".join(parts).
  4. Initialising Kadane's best to 0. For an all-negative array the answer is the largest element, not 0.
  5. Ignoring case and spaces in palindrome or anagram problems. Normalise with lower-casing and filtering when the question says to ignore them.

Practice now: https://www.testsworld.com/mocks

Ready to practise Arrays & strings?
Take a free mock test

Related guides