Introduction to DSA in C++

1. What is DSA?

DSA ki full form hoti hai Data Structure and Algorithm, ye two different things hoti hai jo saath mein use kari jati hai. Ye do cheezein programming mein backbone ka kaam karti hain.

Data Structures:

Ye ek tareeka hota hai data ko memory mein efficiently store karne ka, jisse ham us data ko fast access and retrieve kar sakte hai. Jaise:

Array – Array data ko contigous fashion mein store karta hai.
Linked List – Linked list mein data node ki form mein store hota hai.
Stack, Queue, Tree, Graph etc. – Har Data Structure ka koi specific use hota hai. Jo ham series mein padhenge.

Algorithms:

Algorithms ka matlab hota hai kisi bhi problem ko step by step solve karna, ye main logic hota hai jo ham kisi bhi problem ko efficiently solve karne ke liye use karte hai. Jaise:

Searching
Sorting
Recursion
Dynamic Programming

Note: Ham in Algorithms ko bhi is series mein padhenge.

2. Importance of DSA

1. Enhance Problem Solving Skills:

DSA hamari problem solving skills ko enhance karta hai aur hame koi bhi problem solve karne ke liye ek systematic approach provide karta hai.
Ye hame sikhata hai ki kisi problem ko kese analyze karna hai, uska best solution kiya hoga aur kisi problem ko solve karne ke liye konsa data structure ya algorithm use karni chahiye.

2. Crack Big Company Interview:

DSA hame Big Companies like Google, Amazon, Facebook, Apple, Netflix ke interview crack karne mein help karta hai.
MNC's mein coding rounds hote hai jisme DSA ke 2-3 questions solve karne hote hai.
Companies ke Technical round mein bhi DSA par based questions puche jaate hai.

3. Efficient System Design and Improve Performance:

DSA ki helps se developers efficient code likh paate hai, jo fast run hota hai kam memory ko use kare.
Databases ke schemas design karne mein bahut helpful hota hai. Schemas design karte time hame best data structure ko use karna chahiye iski bhi understanding bhi hame DSA se hi milti hai.

3. Setting up C++ for DSA (IDE & Compilation)

As you know ham is series mein DSA C++ ke sath karne wale even though DSA koi language dependent nhi hota hai, ham ye kisi bhi programming language mein kar sakte hai lekin phir bhi ham is series mein C++ ka use karne wale hai aur apna code C++ mein likhenge.

Why C++

Performance: C++ ki performance bahut hi high hai jisse ham isme complex algorithms ko bhi fast execute kar paate hai.
Object Oriented Programming: C++ ek Object Oriented Programming language hai , jisse ham Data Structure ko implement karne ke liye classes ka use karte hai. Isse code bahut hi organized, modular and easy to understand ban jaata hai.
Standard Template Library (STL): C++ mein bahut saari STL available hai, jo pre-built data structure and algorithm provide karati hai, ham in libraries ka use se kar sakte hai without creating from scratch.

Setting Up C++

C++ ko run karne ke liye hame pehle C++ compiler aur code editor ko download karna padega. Is installation ko setup karne ke liye aap is article ko refer kar sakte hai. Setting up the Environment of C++

4. Time and Space Complexity

Computer Science mein Time and Space complexity fundamental concepts hai ke jo hamari help karte hai ye analyze mein ki koi algorithm kitni efficient hai ? In complexities ko samjh kar ham effiecient code likh sakte hai.

Ye three types ki hoti hai, Best Case, Average Case, and Worst Case. Ham mostly Worst Case ke baare mein padhenge because agar hamne ek baar Worst Case handle kar liya to Best Case aur Average Case automatically cover ho jayenge.

Time Complexity

Time Complexity ka matlab hai wo time jo ek algorithm kisi function ko complete karne mein leti hai kisi bhi input size par.

Common Time Complexities:

1. O(1) - Constant Time: Ye sabse achi time complexity hoti hai, kioki ye constant hai sirf ek hi operation karna padta hai. Ye operation complete hone mein constant time lege.

int getFirstElement(const vector<int>& arr) {
    return arr[0];  // Single operation regardless of array size
}

2. O(n) - Linear Time: Ye Linear complexity hoti hai. Isme algorithm n times leti hai. Iska matlab jab function mein n operation perform hote hai, like for loop, array traversal and searching etc.

int sumArray(const vector<int>& arr) {
    int sum = 0;
    for(int num : arr) {  // Loop runs n times
        sum += num;
    }
    return sum;
}

3. O(n²) - Quadratic Time: Ye complexity doubled up hoti hai linear time complexity ke, iska matlab ye linear algorithm ke comparision mein double time legi. In algorithms mein mostly two loops run hoti hai, ya matrix traversal hota hai.

void bubbleSort(vector<int>& arr) {
    for(int i = 0; i < arr.size(); i++) {         // Outer loop: n times
        for(int j = 0; j < arr.size()-1; j++) {   // Inner loop: n times
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

4. O(log n) - Logarithmic Time: Ye complexity thodi complex hai lekin sabsi achi hai after constant. Mostly computer scientist is algorithm mein solution ko find out karne ka try karte hai. Ye algorithm better isliye hoti hai kioki ye half time mein solution find kar deti hai. Ye algorithm mostly binarySearch, binaryTree jaisi problems mein useful hoti hai jaha par data sorted hota hai bas hame searching implement karni hoti hai.

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size()-1;
    while(left <= right) {           // Halves search space each iteration
        int mid = left + (right-left)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] < target) left = mid+1;
        else right = mid-1;
    }
    return -1;
}

Space Complexity

Space complexity ka matlab hai wo memory space jo ek algorithm ko zarurat padti hai kisi bhi input ko store karne mein.

1. O(1) - Constant Space

int findMax(const vector<int>& arr) {
    int max = arr[0];  // Uses fixed amount of space
    for(int num : arr) {
        if(num > max) max = num;
    }
    return max;
}

2. O(n) - Linear Space

vector<int> copyArray(const vector<int>& arr) {
    vector<int> result(arr.size());  // Creates new array of size n
    for(int i = 0; i < arr.size(); i++) {
        result[i] = arr[i];
    }
    return result;
}

3. O(n²) - Quadratic Space

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n));  // n×n matrix
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            matrix[i][j] = i * j;
        }
    }
    return matrix;
}

Mostly cases mein ham sirf problem ki time complexity ko find out kar rahe honge, space complexity bahut hi rarely hi find out karte hai lekin space complexity bhi pata honi chahiye.

Time Complexity of Simple Loops

#include <iostream>
using namespace std;

int main() {
  for(int i = 0; i < 10; i++) {
    cout << i << " ";
  }
  return 0;
}

Time Complexity: O(10) ~ O(1) (Constant)

Practice Questions:

Find time and space complexity of Factorial of a given number
Find time complexity of two while loops.

Share your answer in comment box.