Ever wondered how to store a bunch of similar data in one place? That's where Arrays and Vectors come in handy. They're like organized containers for your data.

What is an Array?

Imagine you have a list of numbers you want to keep together. An array is simply a "collection of similar types of data elements. Think of it as a row of numbered boxes, where each box can hold one item, and all items are of the same type (like all numbers, or all letters).

For example, if an int (integer) takes up 4 bytes of memory, an array storing 5 integers would take 4x5=20 bytes.

How to Use Arrays: The Three Big Questions

How to Create an Array?

You need to tell the computer:
- What type of data it will hold (e.g., int for whole numbers).
- What you want to name your array (e.g., a).
- How many items it can hold (its size).

Syntax: DataType variableName[size];

Example: int a[5]; This creates an array named a that can hold 5 integers. It reserves 20 bytes of memory.

How to Assign Elements ?

You can put values into your array in a couple of ways:
- During Creation (Initialization):
  
  You can give values to your array when you first create it.
  
  Example: int a[5] = {10, 20, 25, 30, 35};
  - Important Note: The number of values you provide must match the array's size. If you try
    
    int b[3] = {1, 2, 3, 4};, it will cause an error because you're trying to put 4 values into an array that can only hold 3 values.
  - If you provide fewer values than the size, the remaining spots will be filled with zeros. For instance, int c[4] = {1, 2}; would create an array c with values 1, 2, 0, 0.
- After Creation :
  
  You can assign values to specific "boxes" (called indices) in the array. Arrays are "zero-indexed," meaning the first box is at index 0, the second at index 1, and so on.
  
  Example:
```
  int a[5];
  a[0] = 10; // Puts 10 in the first spot
  a[1] = 15; // Puts 15 in the second spot
  a[2] = 25; // Puts 25 in the third spot
  a[4] = 30; // Puts 30 in the fifth spot
  // You can leave gaps, but accessing them might give unexpected values.
```
- Using a Loop (for user input):
  
  You can use a loop to let the user enter values into the array.
  
  Example:
```
  for (int i = 0; i < 5; i++) { // Loop 5 times (for indices 0 to 4)
      cin >> a[i]; // Read input into each spot of the array
  }
```

How to Use an Array?

Once you have data in your array, you can access it, process it, and perform operations.

Example: Finding the Maximum Element in an Array

Let's say you have an array a = {10, 15, 5, -3, 2, 11, 3}. Here's how to find the largest number:

 int main() {
     int a[] = {10, 15, 5, -3, 2, 11, 3}; // Our array 
     int max = a[0]; // Assume the first element is the largest initially

     // Loop through the rest of the array (starting from the second element)
     for (int i = 1; i < 7; i++) {
         if (max < a[i]) { // If the current element is larger than our current 'max'            
             max = a[i];   // Update 'max' to this new larger element
         }
     }
     cout << "Max element is " << max; // Print the result
     return 0;
 }

Introducing Vectors (from STL)

While arrays are great, they have a fixed size once created. What if you don't know how many items you'll need, or the number changes? That's where Vectors come in! Vectors are part of the C++ Standard Template Library (STL) and are like dynamic arrays – they can grow or shrink in size as needed.

To use vectors, you need to include the <vector> header. It's also common to use using namespace std;.

Basic Vector Operations:

Creating a Vector:

vector<int> v; This creates an empty vector named v that can hold integers.
Adding Elements:

v.push_back(2); This adds the value 2 to the end of the vector v. push_back is very useful for adding elements without worrying about capacity.
Accessing Elements:

You can access elements using their index, just like arrays:

cout << v[2]; (This would print the element at index 2).

Advanced Array/Vector Concepts

Some interesting problems related to arrays/vectors for more understanding :

Removing Duplicates from a Sorted Array (In-Place)

This task often means modifying the original array to contain only unique elements, keeping them in order, and returning the new length.

One approach involves using a temporary array:

int removeDuplicate(int a[], int n) { // a[] is the array, n is its size
    if (n == 0) return 0; // Handle empty array case

    int temp[n]; // Create a temporary array 
    temp[0] = a[0]; // The first element is always unique 
    int k = 1;      // k will track the number of unique elements

    // Loop from the second element onwards
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i-1]) { // If current element is same as previous (a duplicate)
            continue;         // Skip it
        } else {
            temp[k] = a[i]; // If unique, add it to the temporary array
            k++;            // Increase count of unique elements 
        }
    }

    // Copy unique elements back to the original array
    for (int i = 0; i < k; i++) {
        a[i] = temp[i];
    }
    return k; // Return the new length
}

This method uses extra space for the temp array. An "in-place" solution would modify the array without using extra space, often by shifting elements directly.

"Plus One" Operation on a Number Represented as Digits in a Vector

Imagine you have a number like 123 represented as a vector<int> digits = {1, 2, 3}. The task is to add one to this number.

vector<int> plusOne(vector<int>& digits) { // 'digits' is our number as a vector
    int n = digits.size(); // Get the number of digits 

    // Start from the last digit and go backwards
    for (int i = n - 1; i >= 0; i--) {
        if (digits[i] < 9) { // If the current digit is less than 9 (e.g., 679) 
            digits[i]++;     // Just increment it (e.g., 680) 
            return digits;   // We are done, return the result
        } else {
            digits[i] = 0; // If it's a 9, set it to 0 (e.g., 999 becomes _00) 
        }
    }
    // If we reach here, it means all digits were 9 (e.g., 999).
    // We need to add a new leading 1 (e.g., 999 + 1 = 1000). 
    digits.insert(digits.begin(), 1); // Insert 1 at the beginning
    return digits;
}

Merging Two Sorted Arrays (into the first array)

This problem often involves merging num2 into num1, assuming num1 has enough space at the end. The notes show a typical approach starting from the end of both arrays to avoid overwriting elements prematurely.

Let's assume num1 has a size of 6, and num2 has a size of 3. We want to merge num2 = {2, 5, 6} into num1 = {1, 2, 3, _, _, _} resulting in {1, 2, 2, 3, 5, 6}.

// Assuming num1 has enough capacity (m+n)
void mergeSortedArrays(int num1[], int m, int num2[], int n) {
    int k = m + n - 1; // Pointer for the last position in num1 
    int i = m - 1;     // Pointer for the last element in num1's actual data 
    int j = n - 1;     // Pointer for the last element in num2 

    // While both arrays still have elements to compare 
    while (i >= 0 && j >= 0) {
        if (num1[i] > num2[j]) { // If element in num1 is greater 
            num1[k] = num1[i];   // Place it at the end of num1 
            i--;                 // Move num1 pointer back 
        } else {
            num1[k] = num2[j]; // Else, element in num2 is greater or equal 
            j--;               // Move num2 pointer back         }
        k--; // Move the 'write' pointer back in num1    }

    // If there are remaining elements in num2 (meaning num1 ran out first) 
    while (j >= 0) {
        num1[k] = num2[j]; // Copy remaining elements from num2 to num1 
        j--;               // Move num2 pointer back 
        k--;               // Move 'write' pointer back
     }
}

Understanding Arrays and Vectors