Competitive programming often looks like a race to write code as fast as possible. But the real secret is simpler: the best competitive programmers are not just faster typists — they are better at choosing the right data structure, the right algorithm, and the right complexity level for the job.
Before we jump into recursion, dynamic programming, graphs, or those problems that make your brain do backflips, we need a solid base. This first session is exactly that.
Let's begin. 🚀
1. Data Types: What Kind of Data Are You Storing?
A data type tells a programming language what kind of value a variable holds and what operations are valid on it.
Primitive Data Types
The basic building blocks provided by the language itself:
-
Integer — whole numbers:
5,100,-3 -
Float / Double — decimal values:
3.14,99.5 -
Character — a single symbol:
'A','z' -
Boolean —
trueorfalse
User-Defined Data Types
When primitive types are not enough, programmers define their own:
- Structs — group related fields under one name
- Classes — structs with behaviour (methods) attached
- Enums — a fixed set of named constants
- Typedefs / Aliases — rename existing types for clarity
A Real-World Example
Imagine building a food delivery app:
- An integer stores the number of items in the cart
- A float stores the total bill amount
- A boolean tracks whether the order has been delivered
- A class represents an entire
Order— customer name, address, items, payment status
Data types are essentially the labels on your containers. Without them, chaos begins early.
2. Data Structures: How Do You Organise Data?
If data types answer what a value is, data structures answer how to organise many values efficiently. This is where competitive programming starts to get interesting.
Linear Data Structures
Elements arranged one after another, like people queuing at a ticket counter:
- Arrays — fixed-size, indexed, fast random access
- Linked Lists — dynamic size, efficient insertions and deletions
- Stacks — last in, first out (LIFO)
- Queues — first in, first out (FIFO)
Non-Linear Data Structures
Data arranged in hierarchies or networks rather than a single sequence:
- Trees / Binary Trees / BSTs — hierarchical relationships
- Heaps — trees optimised for finding the min or max quickly
- Graphs — nodes connected by edges, modelling anything from maps to social networks
A Real-World Example
- A playlist maps naturally to a linear structure
- A company org chart is a tree
- A social network or city road map is a graph
Picking the right structure for a problem is one of the most impactful decisions you'll make in competitive programming. The same problem can be trivial with one structure and brutally hard with another.
3. Abstract Data Types (ADT): What Operations Should a Structure Support?
An Abstract Data Type defines the behaviour of a data structure without specifying how it's implemented internally.
An ADT answers two questions:
- What data does this structure hold?
- What operations can be performed on it?
It does not care whether it's built on top of an array, a linked list, or something else entirely.
Common ADTs
Stack, Queue, Priority Queue, Linked List, Binary Tree, Dictionary / Map, Hash Table, Graph.
Example: The Stack ADT
A stack supports:
-
push— add an element to the top -
pop— remove the element from the top -
peek— look at the top element without removing it
Whether the underlying implementation uses an array or a linked list is irrelevant to anyone using the stack. The behaviour is what matters. That's the value of abstraction: less noise, more clarity.
4. Algorithms: The Step-by-Step Solution
An algorithm is a finite, well-defined sequence of steps to solve a problem.
Examples you'll encounter constantly in CP:
- Sorting a list of numbers
- Searching for a value
- Finding the shortest path in a graph
- Counting combinations or permutations
A Real-World Example
Making tea is an algorithm:
- Boil water
- Add tea leaves
- Add sugar and milk
- Strain and serve
Competitive programming uses the same idea — just with code instead of a kettle, and much stricter time limits.
5. Analysis of Algorithms: Which Solution Is Actually Better?
Most problems can be solved in more than one way. Algorithm analysis helps you decide which approach is worth implementing.
Two primary dimensions:
- Time complexity — how fast does it run?
- Space complexity — how much memory does it consume?
A solution can be completely correct and still fail in a contest because it's too slow for large inputs. In CP, that is the difference between AC (Accepted) and TLE (Time Limit Exceeded). Correctness is necessary but not sufficient.
There is also a classic tradeoff worth keeping in mind: faster algorithms often use more memory, and memory-efficient algorithms are often slower. Knowing when to trade one for the other is a skill that develops over time.
6. Runtime Analysis: How Does Time Grow With Input?
Runtime analysis studies how an algorithm's execution time changes as input size increases.
If the input size doubles, does the running time:
- barely change?
- double?
- quadruple?
- explode exponentially?
That is the central question. The answer determines whether your solution will pass within the contest's time limit or grind to a halt on large test cases.
7. Rate of Growth: How Quickly Does Running Time Increase?
The rate of growth describes how an algorithm's cost behaves as input size approaches infinity. Not all algorithms grow at the same speed — and the differences can be dramatic.
From slowest to fastest growth:
1 < log log n < log n < (log n)² < n < n log n < n² < n³ < 2ⁿ < 4ⁿ < n! < 2^(2ⁿ)
In practice, these are the growth rates you'll reason about most often:
Complexity Name Typical example
──────────────────────────────────────────────────────────────────────
O(1) Constant Inserting at the front of a linked list
O(log n) Logarithmic Binary search on a sorted array
O(n) Linear Linear scan through an unsorted array
O(n log n) Linearithmic Merge sort, heap sort
O(n²) Quadratic Nested loops over a list
O(n³) Cubic Naive matrix multiplication
O(2ⁿ) Exponential Recursive subset enumeration
One important note: the examples above are simplified. Shortest path, for instance, is not always quadratic — it depends entirely on which algorithm you use and how the graph is represented. This is exactly why understanding why complexity works the way it does matters more than memorising a lookup table.
8. Types of Analysis
The same algorithm can behave very differently depending on the input. That's why we analyse three scenarios:
Best case — the input that causes the algorithm to finish as quickly as possible. Often not very useful on its own, but good for building intuition.
Worst case — the input that forces the algorithm to do the most work. This is what contest judges usually design their test cases around. If your solution handles the worst case, it handles everything.
Average case — expected performance across typical inputs. More relevant for real-world applications than for contests, where worst-case guarantees matter most.
Asymptotic Notations
Three standard notations describe these bounds formally:
- Big-O (O) → upper bound — the algorithm grows no faster than this
- Big-Omega (Ω) → lower bound — the algorithm grows at least as fast as this
- Big-Theta (Θ) → tight bound — the algorithm grows exactly like this, up to constant factors
Simple intuition:
-
O(n²)means: beyond some input size, the runtime will not exceedc × n²for some constantc -
Ω(n²)means: the runtime will always take at least proportional ton² -
Θ(n²)means: the runtime is tightly bounded both above and below byn²
If this feels abstract right now, that is completely normal. It becomes intuitive with practice — especially once you start seeing it applied to real problems.
9. Amortized Analysis: The Average Cost Across Many Operations
Sometimes a single operation is expensive, but the vast majority are cheap. Judging the algorithm by its worst single operation would be misleading.
Amortized analysis looks at the average cost per operation over a long sequence, rather than any one operation in isolation.
Classic Example: Dynamic Arrays
Most insertions into a dynamic array (like Python's list or C++'s vector) are O(1) — just write to the next slot.
But occasionally the array fills up and must resize — copying all elements to a new, larger block. That one operation is O(n).
Amortized analysis shows that if you average the resize cost across all the cheap insertions that came before it, the per-operation cost is still O(1). The expensive step is "paid for" by all the cheap ones that preceded it.
This is why vector::push_back is considered O(1) amortized even though individual resizes are not.
Why This Foundation Matters
Recursion, greedy algorithms, dynamic programming, trees, graphs — everything in competitive programming is built on top of these ideas. Skipping the foundation doesn't save time; it just means hitting a wall later when the concepts are assumed rather than explained.
Once these ideas are familiar — data types, data structures, ADTs, algorithm analysis, growth rates, amortized thinking — the rest of CP becomes significantly easier to learn because you already speak the language.
What's Next
Session 2 will cover one of the most important and widely-used tools in competitive programming: recursion.
It will be fun — in a slightly brain-bending but very useful kind of way. 🐇
If this was helpful, bookmark it as your CP foundation reference before the recursive rabbit hole begins. More sessions coming — follow along to stay in sync.
This series is my attempt to document what I'm learning as I go deeper into data structures and algorithms. I've drawn from several resources along the way — lecture notes, online courses, and community discussions — with Data Structures and Algorithms Made Easy by Narasimha Karumanchi being one of the most structured references I've come across. The explanations, analogies, and examples throughout are my own interpretation. If a concept resonates, I'd encourage picking up the book — it goes far deeper than any article can.
Top comments (0)