Know this before you start: “Build a new string or array from an answer”
Building a new string or array as the answer
Collect pieces in a list and join (or return) it at the end. Strings can't change in place, so adding to one in a loop silently costs O(n²).
The idea
Many problems ask you to produce something new: a reversed string, a filtered list, a merged result. The clean way is an empty list you append to as you go; appending is O(1).
Strings are immutable in Python, Java and JavaScript: result += ch makes a whole new string every time, copying everything so far. Over a loop that adds up to O(n²). Append to a list and "".join(parts) once instead.
See it step by step
Keep only the letters of “a1b2c3”, uppercased
- parts = []
- 'a' → append 'A'; '1' → skip; 'b' → append 'B'; '2' → skip; 'c' → append 'C'; '3' → skip
- "".join(['A', 'B', 'C']) → "ABC", built in one pass.
In code (Python)
def letters_upper(s):
parts = []
for ch in s:
if ch.isalpha():
parts.append(ch.upper())
return "".join(parts)
def evens(nums):
return [x for x in nums if x % 2 == 0] # a new list in one line
print(letters_upper("a1b2c3")) # ABC
print(evens([1, 2, 3, 4])) # [2, 4]O(n) time and O(n) space for the answer.
When you'll use it
- Reversing words, compressing or encoding strings, filtering or merging arrays.
- Any time the output is a new sequence.
Common mistakes
- s = s + ch in a long loop.
- Modifying the input when the problem expects a new result (or the reverse).
