Codility PHP Quick Reference

Core checklist

• Restate inputs, outputs, constraints.
• Identify complexity target: usually O(N) or O(N log N).
• Pick pattern: prefix sums, hash map, sort + scan, two pointers, stack.
• Edge cases: empty, length 1, all equal, negatives, duplicates, overflow.
• Test: smallest cases, a random case, and a worst-shape case.

If you can explain the invariant while coding, you are less likely to regress.

Common pitfalls (PHP)

• Loose comparisons: use === / !==.
• Undefined indexes: check with isset.
• Sorting: know when keys are preserved, and when values are reindexed.
• Large N: avoid O(N²) loops over arrays.
• Integers: PHP ints are platform dependent, but generally 64-bit on Codility.

O(N)

• Single pass with counters or a hash map.
• Prefix sums, running min/max, Kadane, counting occurrences.
• Stack for brackets, next greater element, monotonic patterns.

O(N log N)

• Sort then scan, sort and merge intervals, greedy by sorted keys.
• Binary search on answer with a feasibility check (often O(N)).

Edge cases checklist

• Sizes: empty, 1 element, 2 elements.
• Shape: already sorted, reverse sorted, all equal.
• Values: negatives, zeros, duplicates, max constraints.
• Ranges: inclusive vs exclusive bounds, 0-based vs 1-based.

Complexity smell test

• If you have two loops over N, assume it is too slow unless the inner loop is amortised.
• If you sort, say why: “sort then scan” often converts O(N²) into O(N log N) + O(N).
• If you use a map/set, name what it stores: membership, frequency, last seen index.

Variable meaning (write it down)

• $l/$r: current window bounds (and what invariant the window must satisfy).
• $P: prefix sums where P[i] means sum of the first i elements.
• $bestEnding: best value “ending at i” (Kadane-style DP).
• $lo/$hi: which bounds are inclusive, and what you return.

PHP gotchas to remember

• strpos(...): always compare with !== false (0 is a valid index).
• sort() reindexes keys. Use asort() if you must preserve keys.
• Prefer === / !== to avoid “0”, false, and "" surprises.
• Initialise $min/$max safely with PHP_INT_MAX/PHP_INT_MIN.

Prefix sums

• Build P (prefix sums):
• P[0] = 0 [empty prefix]
• P[i + 1] = P[i] + A[i] [so P[k] = sum(A[0..k-1])]
• Range sum for l..r (inclusive):
• sum(l..r) = P[r + 1] - P[l] [convert range sum into two prefix sums]
• Use for: tape equilibrium, average slice, many range queries.

$n = count($A);
$P = array_fill(0, $n + 1, 0);      // [P[0] = 0]

for ($i = 0; $i < $n; $i++) {
  $P[$i + 1] = $P[$i] + $A[$i];     // [P[i+1] = sum(A[0..i])]
}

$sumLR = $P[$r + 1] - $P[$l];       // [sum(l..r)]

Two pointers, sliding window

• Keep l and r, maintain an invariant.
• Move one pointer at a time so total moves are O(N).
• Common for distinct counts, sums within constraints.

$l = 0;                        // [left pointer]
$freq = [];

for ($r = 0; $r < $n; $r++) {
  $x = $A[$r];                   // [right element]
  $freq[$x] = ($freq[$x] ?? 0) + 1;

  while ($freq[$x] > 1) {        // [shrink until invariant holds]
    $y = $A[$l];                 // [element leaving window]
    $l++;
    $freq[$y]--;
  }
}

Stack, brackets

• Use an array as stack: $stack[] = $v, array_pop.
• Match closing to last opening, fail fast.

$stack = [];                   // [open brackets]

foreach (str_split($s) as $ch) {
  if ($ch === "(" || $ch === "[" || $ch === "{") {
    $stack[] = $ch;
    continue;
  }

  if (!$stack) {
    return 0;                    // [closing without opening]
  }

  $top = array_pop($stack);

  if ($ch === ")" && $top !== "(") return 0; // [mismatch]
  if ($ch === "]" && $top !== "[") return 0; // [mismatch]
  if ($ch === "}" && $top !== "{") return 0; // [mismatch]
}

return $stack ? 0 : 1;           // [must close all opens]

Kadane (max subarray)

• bestEnding: best sum ending here.
• best: best overall.

$bestEnding = $A[0];           // [best sum ending at i]
$best = $A[0];

for ($i = 1; $i < $n; $i++) {
  $bestEnding = max($A[$i], $bestEnding + $A[$i]); // [extend or restart]
  $best = max($best, $bestEnding);                 // [global best]
}

return $best;

Binary search (on sorted array)

• Prefer half-open intervals to avoid infinite loops.
• Be explicit about return: index, insertion point, or boolean.

$lo = 0;                       // [inclusive]
$hi = $n - 1;

while ($lo <= $hi) {
  $mid = intdiv($lo + $hi, 2);

  if ($A[$mid] === $target) {
    return $mid;
  }

  if ($A[$mid] < $target) {
    $lo = $mid + 1;               // [search right]
  } else {
    $hi = $mid - 1;               // [search left]
  }
}

return -1;

Binary search on answer

• Monotonic predicate ok(x), search smallest x that works.
• Often used for min max division, earliest time, minimum capacity.

$lo = $minCandidate;           // [lower bound]
$hi = $maxCandidate;

while ($lo < $hi) {
  $mid = intdiv($lo + $hi, 2);

  if (ok($mid)) {
    $hi = $mid;                   // [mid works, try smaller]
  } else {
    $lo = $mid + 1;               // [mid fails, go bigger]
  }
}

return $lo;

Counting, sets, missing elements

• Use a boolean set or frequency map.
• If values are 1..N, you can use an array of booleans for speed.
• XOR trick: pairwise cancel (only when exactly one unpaired exists).

// XOR unpaired (OddOccurrencesInArray style)
// [assumes: exactly one value occurs odd times]

$x = 0;

foreach ($A as $v) {
  $x = ($x ^ $v);   // [pairs cancel: a^a = 0]
}

return $x;          // [remaining unpaired value]

Sorting + scan

• Good for distinct counts, triangle checks, minimal differences.
• After sorting, many problems become linear scans.

sort($A);                      // [group equal values]

$distinct = 0;
$prev = null;

foreach ($A as $v) {
  if ($prev === null || $v !== $prev) {
    $distinct++;                  // [new value]
  }

  $prev = $v;
}

Overflow, big sums

• Keep sums in integers, avoid float.
• Use PHP_INT_MAX guards for initialisation.
• For products, check constraints or use comparisons that avoid multiplication.

Useful one-liners

• $x = ($map[$k] ?? 0) + 1; [increment counter in a map]
• $arr = array_fill(0, $n, false); [boolean array size N]
• $mid = intdiv($lo + $hi, 2); [binary search midpoint]
• $min = min($min, $v);, $max = max($max, $v); [running min/max]

If you freeze

• Write a brute force version in your head, then remove one loop.
• Ask: can I sort, prefix-sum, hash, or slide a window?
• Identify the invariant you need to maintain.
• Restate: “Given X, return Y”, and write down constraints (N, range, target complexity).
• Pick a pattern: sort + scan, prefix sums, set/map, two pointers, stack, binary search on answer.
• Do 3 tiny runs: step through 2–3 iterations and track variables on paper.
• Off-by-one check: explicitly note inclusive vs exclusive ranges and 0-based vs 1-based indices.

Micro tests

• Smallest input, and a slightly larger input with duplicates.
• A case that hits every branch, especially while-loops.
• Random case and a worst-shape case (sorted ascending, descending, all same).