Arrays and Strings for Coding Interviews

Interviewers expect you to know that an array reads any index in O(1) but inserts or deletes in the middle in O(n), that a dynamic array's append is amortized O(1), and that strings are immutable in Python, JavaScript and Java, so changing one builds a new one. Most questions then test in-place edits and index scans.

Operations and what they cost

Operation	Time	Why
Read or write by index	O(1)	The position is computed from the start address.
Append to a dynamic array	O(1) amortized	The occasional resize copies everything, spread across many appends.
Insert or delete at index i	O(n - i)	Everything after i has to move.
Search, unsorted	O(n)	You may have to look at every element.
Search, sorted	O(log n)	Binary search halves the range each step.
Reverse or filter in place	O(n)	One pass with two pointers, O(1) extra space.
Slice of length k	O(k)	A slice copies, in most languages.
Concatenate two strings	O(len a + len b)	A new string is built.
Build a string with repeated `+`	O(n²) in total	Each step copies everything so far.

Those are the costs of the structures. For the language figures, the Python table and the Java Javadoc state them directly. The JavaScript documents give no Big O for Array or string methods, so there you state your assumption.

When to reach for it

You need to reach a position directly, by index, and not walk to it.
The answer is a contiguous range, which points to a sliding window.
The input is sorted, or sorting it would make the question easy.
The question says in place, or asks for O(1) extra memory.
A string question is about character counts or positions: the string is really an array of characters.

What immutable strings change

Each language documents this. Python calls strings "immutable sequences of Unicode code points." Java says "Strings are constant; their values cannot be changed after they are created." MDN says all types except Object define immutable values, which includes strings.

The interview consequence is the same in all three: you cannot edit a character in place, and a loop of s += c keeps building new strings. Python's documentation says that is quadratic in the total length. So collect the pieces and join them at the end, or work on an array of characters. Java has StringBuilder, a mutable sequence of characters, for exactly this.

How it looks in Python, JavaScript and Java

The same two jobs in each language: run-length encode a string by building the output in pieces, then remove duplicates from a sorted array in place.

def run_length(s):
    parts = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        parts.append(s[i] + str(j - i))
        i = j
    return "".join(parts)          # never s += ... in a loop

def dedupe_sorted(nums):
    """Removes repeats in place and returns the new length."""
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

JavaScript

function runLength(s) {
  const parts = [];
  let i = 0;
  while (i < s.length) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    parts.push(s[i] + (j - i));
    i = j;
  }
  return parts.join("");
}

function dedupeSorted(nums) {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read];
  }
  return write;
}

Java

class ArraysAndStrings {
    static String runLength(String s) {
        StringBuilder out = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            out.append(s.charAt(i)).append(j - i);
            i = j;
        }
        return out.toString();
    }

    static int dedupeSorted(int[] nums) {
        if (nums.length == 0) return 0;
        int write = 1;
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[write - 1]) nums[write++] = nums[read];
        }
        return write;
    }
}

In Java, an int[] has a fixed size, and ArrayList is the dynamic version, with an add documented as amortized constant time. In Python, the language's FAQ on lists describes a list as a variable-length array of references, so it is the dynamic version already.

How to explain the choice out loud

What a strong candidate might say

I'll filter in place with two indexes, because the question asks for O(1) extra memory and the array is sorted, so any repeat sits right next to the value it repeats. The read index scans everything, and the write index marks the end of the part I've kept. Each element is read once, so it's O(n) time with O(1) extra space. Strings are immutable here, so if this were a string, I'd collect the pieces in a list and join them at the end to avoid quadratic copying.

Common mistakes

Building a string with += in a loop and calling it O(n).
Inserting or deleting at the front of an array inside a loop, which makes the loop quadratic.
Slicing inside a loop or a recursion, and forgetting that each slice copies.
Off-by-one errors on ranges: decide whether the end is inclusive, and say so.
Treating a string's length as its number of characters. In JavaScript and Java it counts UTF-16 units, so ask about non-ASCII input.

Where to go next

Patterns: arrays and hashing, two pointers and sliding window.
Worked problems: Deduplicate a Member's Skills, Reach a Promotion Threshold from a Cart and Deduplicate a Stream of Retried Events.
All the figures in one place: the Big O cheat sheet.
Practice saying it: a coding mock interview.