Gain insights into competitive programming, explore C++ skills with theory, code samples, practice problems, and master faster implementation for contests like ACM ICPC, Google CodeJam, and HackerCup.

Competitive programming can be a great way to build out your programming skills, get on any major company’s radar, and earn a little extra cash along the way.

In this course, you will learn to prepare for competitive programming contests like ACM ICPC, Google CodeJam, Facebook HackerCup, and many more.

Each topic is broken down with a healthy mix of theory, code samples, step-by-step solved sample problems, illustrations, useful practice problems, and tips and tricks for faster implementation.

You will need some solid C++ foundations coming into this course, but by the end it, you will be confident enough in your C++ skills to take home the win.

Competitive Programming in C++: The Keys to Success

# Array vs Vector 
Many times, you need a structure like an array that is dynamic in size. Vectors are dynamic arrays. Vectors, similar to an array, have contiguous memory allocation so that random access is $O(1)$ for vectors as well.
 
One way to implement vectors using an array is to copy the array to a new array of double the size every time the first array is full. The amortized time complexity is $O(1)$ for inserting elements in such a case.

---

# Time complexity
Time complexity for vector operations are the same as arrays:

* Inserting at end - $O(1)$
* Inserting in between - $O(N)$
* Deleting last node - $O(1)$
* Deleting other nodes - $O(N)$

---

# Operations
Here are some operations on vectors that we will be using very frequently. Read [this](http://www.cplusplus.com/reference/vector/vector/) for a complete documentation on vectors.

**Include statement**: ```#include <vector>```

Please make sure you understand important vector methods and how to deal with iterators. This course will not go over these C++ concepts.

```
vector<int> v; // new empty vector
vector<int> v(5); // new vector of size 5
vector<boolean> v(5, true); // new vector of size 5 with all values initialized to true

v.size(); // get size
v[i]; // access ith element

v.push_back(x); // insert x at end of vector
v.pop_back(x); // delete last element

v.begin(); // get iterator to beginning
v.end(); // get iterator to end (theoretically, the element after the last element)

v.erase(v.begin() + 4); //delete 4th element

sort(v.begin(), v.end()) //sort vector
reverse(v.begin(), v.end()) // reverse the vector
```

---





In this lesson, we'll compare vectors with arrays and see how to use C++ STL Vector.


Introduction

Complexity Analysis

Number Theory

Arrays and Vectors

Sieve of Eratosthenes

Strings

Sorting

Linked List

Stack

Queue

Binary Tree

2 Pointers

Heap

Binary Search Tree

Balanced Binary Search Tree

Course Conclusion

Vectors

Array vs Vector