Skip to main content

Arrays and Vectors

Introduction to Array and Vector#

If you are someone not new to competitive programming, a quick overview of the introduction should do, but if you are a beginner read carefully and understand about array and vector as these are data structures that you will be using in almost every programming problem you solve.

Tips

Vector compared to Array is more versatile and flexible, along with the utilities provided for vectors by STL makes them easy to work with. The following STL utilities for vectors in C++ are a must know : resize(), size(), push_back(), pop_back(), begin(), end(), sort(). Do read about what they do while learning about vectors.

Time Complexity of Insert in Vector#

Now you know what a vector is, but do you know about the time complexity of insert operation in a vector. For arrays it is but simple O(1), is it the same case with vectors, what do you think? Here is a spoiler, the time complexity is not exactly O(1) but the amortised TC is O(1). So what does it mean and what is the significance? Read on and you will find out. First there is introduction of amortised time complexity followed by time complexity of insert operation in vectors.

Q: What is the time complexity of delete in vectors? If you have understood well enough you should be able to answer this.

Dynamic declaration of Array#

From what you have learnt so far about arrays, you can declare arrays and vectors if you know the size, but in many real life scenarios and programming problems, you will not know the size beforehand not until the runtime, so you will need to allocate memory to arrays dynamically using the new keyword.

Declaration and Initialising a Vector#

This may seem very trivial, but doing this trivial thing properly will reduce your multiple lines of code to a single line and improve your coding speed, unless you want to be left behind in a competition it is advised to go through and read about the various ways of vector initialisation.

Tips

Initialise the vector with a default value during its declaration, whenever possible.

Pass by Reference vs Value vs Pointer#

Passing parameters to functions is something you will do all the time, to be able to do it correctly and obtain the correct result from your method you will need to know and understand this fundamental concept. Here you will learn about these concepts from C++ point of view.

Q. What will happen when you pass an array to a function by value? Ponder over this, find the answer and remember it.

Passing of Array and Vector to Functions#

Now that you have learnt about the differences between pass by reference, value and pointer, here you will learn about passing of array and vector to functions.

Passing an array by value is a little tricky so understand clearly what happens when you pass an array by value, well at least you think you are passing by value, but is it really being passed by value? Read on to find out

Caution

When you do not pass an array by reference to a function, it decays into pointers, so the changes that you do in the function will be reflected back, the same is not true for vectors

Q: How is a pointer similar to an array? Know Here

Questions#

Array Rotation#

QUESTION

Prefix/Suffix Array#

Two Pointers#

Kadane's Algorithm#

Bucketing#

Sorting#

QUESTION

Random#