Skip to content
CCC Python Course

Linear-pass thinking and hidden costs of built-ins

Stage
3
Module
M3.9
Lessons
1

In this module

  • Solve problems by scanning data once instead of searching repeatedly.
  • Recognize when calling a built-in function does extra work.
  • Apply the two-pointer technique to solve problems in one pass.
  • Reason about time complexity to avoid slow solutions.

Before this module

M2.9Complexity analysis and deriving the target from N

Lessons

  1. 1Linear pass thinking and hidden costs of built-ins

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2018 S1
    Voronoi Villages (opens on DMOJ in a new tab) DMOJ

    Track a running minimum while scanning a sorted list once.

    Why DMOJ: A one-pass tracking problem in the same style as this lesson's min/max example.

  2. 2021 J3
    Secret Instructions (opens on WMOJ in a new tab) WMOJ

    Read input until a sentinel value appears, without knowing the count in advance.