skip to content

The `in` operator works on both ranges and collections (e.g. `x in list`). How do these differ in semantics and performance, and what surprises can `in` produce with strings and reversed ranges?

level: middleimportance: should knowfreq 52%

answer

  1. `in` is `contains` for every receiver
  2. range O(1), List O(n), Set ~O(1), String = substring
  3. reversed `10..1` is empty -> `5 in 10..1` is false
  4. `"ab" in "abc"` is substring true
  5. List membership in a loop -> convert to Set

basics

~20 s

in always calls contains. For a range it's a quick comparison; for a list it scans elements (equals); for a Set it's a fast hash lookup; for a String it checks substrings. Reversed numeric ranges are empty.

solid answer

~50 s

`x in y` is `y.contains(x)` for every type. The *cost* depends on the receiver's `contains`: a numeric **range** is O(1) (compare to `first`/`last`); a **List** is O(n) linear scan using `equals`; a **Set/Map keys** is ~O(1) hash lookup; a **String** with a `String` argument does a `contains` substring search, and with a `Char` argument checks character presence. Surprises: (1) a *reversed* numeric range like `10..1` is **empty**, so `5 in 10..1` is false — people expect it to auto-correct, but `..` doesn't (use `downTo` for descending iteration, though that's a sibling topic). (2) `"ab" in "abc"` is true (substring), which differs from list-element semantics. (3) `in` on a huge `List` in a loop is an accidental O(n*m) trap — convert to a `Set` first. Choosing the receiver type is therefore a correctness *and* performance decision.

code

kotlin · 9 lines
kotlin
val allowedIds = (1000..1999)            // O(1) membership
val blockedNames = hashSetOf("root", "admin")

fun canAccess(id: Int, name: String): Boolean =
    id in allowedIds && name !in blockedNames

println(canAccess(1500, "alice"))  // true
println(canAccess(1500, "root"))   // false
println(5 in 10..1)                 // false (empty reversed range)

go deeper

for a junior

Knows in works on both ranges and collections and returns Boolean.

for a middle

Articulates the cost differences (range O(1) vs List O(n) vs Set ~O(1)) and the String substring surprise.

for a senior

Proactively picks range/Set/List by access pattern and spots the O(n*m) loop trap.

for a principal

Frames receiver choice as an API/perf contract and guides team conventions for membership-heavy code.

## One operator, many `contains` `x in y` is universally `y.contains(x)`, and `x !in y` is `!y.contains(x)`. The semantics and cost come entirely from which `contains` the receiver provides. ## Membership cost by receiver | Receiver | `contains` behavior | Cost | |---|---|---| | `IntRange`/`CharRange` | compare to `first`/`last` | O(1) | | `List` | linear scan with `equals` | O(n) | | `Set` (HashSet) | hash lookup | ~O(1) | | `Map` (via `key in map`) | key hash lookup | ~O(1) | | `String`, arg `String` | substring search | O(n*m) | | `String`, arg `Char` | character presence | O(n) | ```kotlin println(5 in 1..10) // range: O(1) comparison println(5 in listOf(1, 5, 9)) // list: scans elements with equals println(5 in setOf(1, 5, 9)) // set: hash lookup println("key" in mapOf("key" to 1)) // map keys println("bc" in "abcd") // string: substring -> true println('c' in "abcd") // string + Char -> true ``` ## Surprise 1: reversed numeric ranges are empty `10..1` does **not** descend; `..` only builds an ascending closed range. When `start > endInclusive` the range is **empty**: ```kotlin println(5 in 10..1) // false println((10..1).isEmpty()) // true ``` Don't expect membership to "swap" the bounds for you. ## Surprise 2: string membership is substring, not element For a `List<String>`, `"ab" in list` means "is `\"ab\"` one of the elements?". For a `String`, `"ab" in str` means "does `str` **contain** the substring `ab`?". Same operator, different mental model — keep the receiver type in mind. ## Surprise 3: `in list` inside loops ```kotlin // O(n*m): for each candidate, a full list scan val allowed = bigList val hits = candidates.count { it in allowed } // slow // Fix: O(n+m) val allowedSet = bigList.toHashSet() val hits2 = candidates.count { it in allowedSet } // fast ``` Converting a frequently-queried `List` to a `Set` turns repeated O(n) scans into O(1) lookups. ## Takeaway Reach for a **range** when the membership is an interval, a **Set** when it's a fixed lookup table, and remember that `String` membership is substring-based.

  • Why might `it in list` in a hot loop be a performance bug?
    Each `in` is an O(n) scan; over m candidates it's O(n*m). Converting the list to a HashSet makes each lookup ~O(1).
  • Does `"ab" in "abc"` test element equality or substring?
    Substring. `String.contains` searches for `"ab"` inside `"abc"`, returning true.

in is one question — 'are you in here?' — but a range answers by glancing at two fenceposts while a list walks the whole room asking each person.

saying these in an interview costs you the question

  • Assuming `in` has the same cost regardless of receiver type.
  • Expecting `10..1` to iterate or contain values descending.
  • Confusing String substring `in` with list element `in`.
  • Using `in` on a large List repeatedly instead of a Set.

context

resolving links…