Introduction to Arrays

Array ek aisa data structure hai jisme hum fixed size ke similar type ke data ko store karte hain — jaise int, char, float, etc. Ye data memory mein contiguous fashion mein store hota hai. Array mein jo data hota hai use element kehte hai aur har element ek index (subscript) se access hota hai.

int arr[5] = {1, 2, 3, 4, 5};

Yahaan arr[0] = 1, arr[1] = 2 and so on...

Note: Agar aapko array bilkul depth mein samjhne hai like declaration, initialization, and memory layout to aap is article ko refer kar sakte hai. Learn Array in Depth. Why refer this article ? Ye mainly DSA ki series hai to isme basics par kam emphsize kiya jayega.

1. One-Dimensional Arrays (1D Arrays)

One-Dimensional Arrays mein elements single row mein store hote hai, ye bahut hi simple way hota hai data ko store karne ke liye.

Example:

int arr[5] = {10, 20, 30, 40, 50};

Traversal Example:

for(int i = 0; i < 5; i++) {
  cout << arr[i] << " ";
}

One-Dimensional Array mein traversal ke liye hame sirf ek single for loop ki need hoti hai. Isme traverse karna bahut hi easy hota.

2. Two-Dimensional Arrays (2D Arrays)

Two-Dimensional Arrays mein elements matrix ya table ki form mein store hote hai. Yaha do cheezo par hame dihaan dena hota hai number of rows and number of columns.

Example:

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

Traversal Example:

for(int i = 0; i < 2; i++) {
    for(int j = 0; j < 3; j++) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

 3. Multi-Dimensional Arrays

2D se zyada dimensions waale arrays. Jaise:

int arr[2][3][4];  // 3D array

Mostly competitive programming mein use hota hai. But concept clear hona chahiye.

4. Basic Operations

Arrays ke kuch basic operations hote hai jinhe samjhna bahut zaruri hai, aur ye operation koi zyada complex nhi hote lekin important hai kioki arrays ki foundation built karte hai.

1. Insertion:

Array mein kisi position pe element ko insert karna.

#include <iostream>  
using namespace std;  

int main() {  
  int arr[10] = {1, 2, 3, 4, 5};  
  int size = 5;  
  int pos, num;  

  cout << "Current array: ";  
  for(int i = 0; i < size; i++) {  
    cout << arr[i] << " ";  
  }  

  cout << "
Enter position & number to insert: ";  
  cin >> pos >> num;  

  // Shift elements to right  
  for(int i = size; i >= pos; i--) {  
    arr[i] = arr[i-1];  
  }  

  arr[pos-1] = num;  
  size++;  

  cout << "New array: ";  
  for(int i = 0; i < size; i++) {  
    cout << arr[i] << " ";  
  }  
  return 0;  
}  

Output:

Current array: 1 2 3 4 5  

Enter position & number to insert: 3 99  

New array: 1 2 99 3 4 5  

Explanation:

Jab hum kisi specific position par naya element insert karte hain, to hume us position ke baad ke saare elements ko right side shift karna padta hai. Isse ek khaali jagah ban jaata hai jahan hum naya element rakh sakte hain.

for(int i = size; i >= pos; i--) {
  arr[i] = arr[i-1];
}
arr[pos-1] = num;

Example:

Agar array {1, 2, 3, 4, 5} hai aur hume 3rd position pe 99 insert karna hai, to pehle 3, 4, 5 ko right shift karenge, phir 99 ko index 2 par daalenge.

Result: {1, 2, 99, 3, 4, 5}

2. Deletion in Array

Array se kisi element ko delete karna.

#include <iostream>  
using namespace std;  

int main() {  
  int arr[10] = {10, 20, 30, 40, 50};  
  int size = 5;  
  int pos;  

  cout << "Current array: ";  
  for(int i = 0; i < size; i++) {  
    cout << arr[i] << " ";  
  }  

  cout << "
Enter position to delete (1-5): ";  
  cin >> pos;  

  // Shift elements to left  
  for(int i = pos-1; i < size; i++) {  
    arr[i] = arr[i+1];  
  }  

  size--;  

  cout << "Array after deletion: ";  
  for(int i = 0; i < size; i++) {  
    cout << arr[i] << " ";  
  }  
  return 0;  
}  

Output:

Current array: 10 20 30 40 50  

Enter position to delete (1-5): 2  

Array after deletion: 10 30 40 50  

Explanation:

Jab hum kisi position se element delete karte hain, to uske baad wale elements ko left shift karna padta hai, taaki array compact ho jaaye.

for(int i = pos-1; i < size; i++) {
  arr[i] = arr[i+1];
}
size--;

Example:

Agar array {10, 20, 30, 40, 50} hai aur hum 2nd position (i.e., 20) delete karna chahte hain, to 30, 40, 50 ko ek ek step pe left shift kar denge.

Result: {10, 30, 40, 50}

3. Updating Array Elements

Kisi position pe element ko update karna.

#include <iostream>  
using namespace std;  


int main() {  
    int arr[5] = {5, 10, 15, 20, 25};  
    int pos, newVal;  


    cout << "Current array: ";  
    for(int i = 0; i < 5; i++) {  
        cout << arr[i] << " ";  
    }  


    cout << "
Enter position & new value: ";  
    cin >> pos >> newVal;  


    // Update element  
    arr[pos-1] = newVal;  


    cout << "Updated array: ";  
    for(int i = 0; i < 5; i++) {  
        cout << arr[i] << " ";  
    }  
    return 0;  
}  

Output:

Current array: 5 10 15 20 25  

Enter position & new value: 4 99  

Updated array: 5 10 15 99 25  

Explanation:

Update ka matlab hota hai kisi particular index par existing value ko replace kar dena kisi naye value se.

arr[pos-1] = newVal;

Example:

Array {5, 10, 15, 20, 25} mein agar 4th position par 99 update karna hai to 20 ko hata ke 99 rakh denge.

Result: {5, 10, 15, 99, 25}

4. Searching in Array

Kisi element ko array mein dhundhne ke liye ham Search operation use karte hain.

#include <iostream>  
using namespace std;  

int main() {  
  int arr[] = {5, 3, 7, 9, 2};  
  int key, found = 0;  

  cout << "Enter element to search: ";  
  cin >> key;  

  // Linear Search  
  for(int i = 0; i < 5; i++) {  
    if(arr[i] == key) {  
      cout << key << " found at index " << i << endl;  
      found = 1;  
      break;  
    }  
  }  

  if(!found) {  
    cout << key << " not found in array!" << endl;  
  }  
  return 0;  
}  

Output

Enter element to search: 7  

7 found at index 2  

Explanation:

Note: Seaching mainly two types ki hoti hai, jo ham aage is series mein details mein samjhenge.

Hum Linear Search technique ka use karte hain jisme hum array ke har element ko ek ek karke check karte hain jab tak matching value mil jaaye.

for(int i = 0; i < 5; i++) {
  if(arr[i] == key) {
    // found
  }
}

Example:

Agar array {5, 3, 7, 9, 2} hai aur hum 7 search kar rahe hain, to loop chalega:

• 5 – match nahi
• 3 – match nahi
• 7 – match ho gaya, output de do

Output: 7 found at index 2

Important Array Questions

1. Prefix Sum (Running Sum):

Question: Ek array diya gaya hai, har index pe uss index tak ke sab elements ka sum store karna hai yahi "Prefix Sum" kehta hai.

Approach:

1. Ek naya prefix array banayenge.
2. Pehla element same rahega.
3. Har next element ke liye previous prefix sum + current element.

Code:

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int prefix[n];
    
    prefix[0] = arr[0];
    for(int i=1; i<n; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    
    cout << "Prefix Sum Array: ";
    for(int i=0; i<n; i++) {
        cout << prefix[i] << " ";
    }
    return 0;
}

Output:

Prefix Sum Array: 1 3 6 10 15

Explanation:

• prefix[0] = arr[0]→ pehla element same
• Loop se har prefix[i] = prefix[i-1] + arr[i] karke sum calculate karte hai
• Time Complexity: O(n)

2. Sliding Window Technique

Question:

Hume ek array diya gaya hai aur ek window size 'k' diya gaya hai. Humein har possible window ka maximum sum nikalna hai.

Example:

• Array: [1, 4, 2, 10, 2, 3, 1, 0, 20]
• Window size (k): 4

Windows and Their Sums:

1. [1, 4, 2, 10] → Sum = 1+4+2+10 = 17
2. [4, 2, 10, 2] → Sum = 4+2+10+2 = 18
3. [2, 10, 2, 3] → Sum = 2+10+2+3 = 17
4. [10, 2, 3, 1] → Sum = 10+2+3+1 = 16
5. [2, 3, 1, 0] → Sum = 2+3+1+0 = 6
6. [3, 1, 0, 20] → Sum = 3+1+0+20 = 24

Expected Output:

Maximum sum among all windows = 24 (last window)

Approach (Kaise Solve Karenge)

Brute Force Approach (Naive Solution)

1. Har possible window ke liye alag se sum calculate karo
2. Maximum sum track rakho

• Problem: Isme har window ka sum alag se calculate karna padega
• Time Complexity: O(n*k) → Bahut slow for large arrays

Optimized Approach (Sliding Window Technique)

1. Pehle Window ka Sum Nikalo: First 'k' elements ka sum calculate karo
2. Window Slide Karo:

• Agla element add karo
• Pichla window ka first element subtract karo

1. Max Sum Update Karo: Har naye sum ko previous max se compare karo

Example Dry Run:

Array: [1, 4, 2, 10, 2, 3, 1, 0, 20], k=4

1. Initial Window (0-3): 1+4+2+10 = 17 (max_sum = 17)
2. Slide Right (1-4): 17 - 1 + 2 = 18 (max_sum = 18)
3. Slide Right (2-5): 18 - 4 + 3 = 17 (max_sum remains 18)
4. Slide Right (3-6): 17 - 2 + 1 = 16 (max_sum remains 18)
5. Slide Right (4-7): 16 - 10 + 0 = 6 (max_sum remains 18)
6. Slide Right (5-8): 6 - 2 + 20 = 24 (max_sum = 24)

Final Answer: 24

Code with Detailed Explanation

#include <iostream>
using namespace std;

int maxSum(int arr[], int n, int k) {
    // Agar array size window size se chota hai
    if(n < k) {
        cout << "Invalid: Array size smaller than window";
        return -1;
    }
    
    // Pehle window ka sum calculate karo
    int window_sum = 0;
    for(int i=0; i<k; i++) {
        window_sum += arr[i];
    }
    
    // Isko hi abhi tak ka maximum maan lo
    int max_sum = window_sum;
    
    // Ab window ko slide karna start karo
    for(int i=k; i<n; i++) {
        // Naya element add karo, pichla window ka first element hatao
        window_sum += arr[i] - arr[i-k];
        
        // Maximum sum update karo
        max_sum = max(max_sum, window_sum);
    }
    
    return max_sum;
}

int main() {
    int arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20};
    int k = 4;
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Maximum sum of any " << k 
         << " consecutive elements is: " << maxSum(arr, n, k);
    
    return 0;
}

Code Explanation:

1. Edge Case Handling: Agar array size window se chota hai toh error return
2. Initial Window Sum: First 'k' elements ka sum calculate kiya
3. Sliding Window:

•  window_sum += arr[i] → naya element add
•  window_sum -= arr[i-k] → pichla window ka first element remove

1. Max Tracking: max() function se har baar maximum sum update kiya

Time Complexity Analysis

• Brute Force: O(n*k) → Har window ka alag se sum calculate karna
• Sliding Window: O(n) → Ek baar array traverse kiya
• Space Complexity: O(1) → Extra space nahi liya

3. Largest Element in Array

Question:

Array mein sabse greatest element find karo.

Approach:

1. First element ko max maan lo
2. Poora array traverse karke har element ko max se compare karo
3. Agar koi bada element mile toh max update karo

Code:

#include <iostream>
using namespace std;

int findMax(int arr[], int n) {
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

int main() {
    int arr[] = {10, 50, 20, 40, 30};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Largest element: " << findMax(arr, n);
    return 0;
}

Output:

Largest element: 50

Explanation:

• Simple linear search se max find kiya
• Time Complexity: O(n)

4. Reverse an Array

Question:

Array ko reverse karo.

Approach:

1. Start aur end pointers le lo
2. Har iteration mein swap karo
3. Start badhao, end ghatao
4. Jab start >= end ho, tab stop ho jao

Code:

#include <iostream>
using namespace std;

void reverseArray(int arr[], int n) {
    int start = 0, end = n-1;
    while(start < end) {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    reverseArray(arr, n);
    
    cout << "Reversed Array: ";
    for(int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Output:

Reversed Array: 5 4 3 2 1 

Explanation:

• Two pointers approach use kiya
• Har step mein start aur end elements swap hote hai
• Time Complexity: O(n)

5. Kadane's Algorithm (Max Subarray Sum)

Question:

Hume ek array diya gaya hai jisme positive aur negative numbers ho sakte hain. Humein contiguous subarray (ek saath adjacent elements) ka maximum sum nikalna hai.

Example:

Array: [-2, -3, 4, -1, -2, 1, 5, -3]

Possible Subarrays and Their Sums:

1. [4] → 4
2. [4, -1, -2, 1, 5] → 4-1-2+1+5 = 7
3. [1, 5] → 6
4. [5] → 5

Expected Output:

Maximum subarray sum = 7 (subarray [4, -1, -2, 1, 5])

Kadane's Algorithm Kya Hai?

• Yeh ek efficient algorithm hai jo O(n) time mein maximum subarray sum find karta hai
• Iska basic idea hai: agar current subarray ka sum negative ho jaye, toh use discard karo aur naye subarray ka start karo
• Yeh dynamic programming ka ek simple application hai

Approach (Kaise Solve Karenge)

Key Concepts:

1. max_ending_here - current subarray ka sum
2. >max_so_far - abhi tak ka maximum sum mila hua

Steps:

1. Initialize max_ending_here = 0 aur max_so_far = INT_MIN (smallest possible value)
2. Array ke har element ke liye:

• max_ending_here mein current element add karo
• Agar max_ending_here > max_max_so_far , toh max_so_far ko update karo
• Agar max_ending_here negative ho jaye, toh use reset karo (0 set karo)

1. Final max_so_far hi hamara answer hoga

Example Dry Run:

Array: [-2, -3, 4, -1, -2, 1, 5, -3]

Initialize: max_ending_here = 0, max_so_far = INT_MIN

1. i=0, arr[0] = -2

• max_ending_here = 0 + (-2) = -2
• max_so_far updates from INT_MIN to -2
• max_ending_here is negative → reset to 0
• State: max_so_far = -2, max_ending_here = 0

2. i=1, arr[1] = -3

• max_ending_here = 0 + (-3) = -3
• max_so_far remains -2 (since -3 < -2)
• max_ending_here is negative → reset to 0
• State: max_so_far = -2, max_ending_here = 0

3. i=2, arr[2] = 4

• max_ending_here = 0 + 4 = 4
• max_so_far updates from -2 to 4
• max_ending_here is positive → keep as 4
• State: max_so_far = 4, max_ending_here = 4

4. i=3, arr[3] = -1

• max_ending_here = 4 + (-1) = 3
• max_so_far remains 4 (since 3 < 4)
• max_ending_here is positive → keep as 3
• State: max_so_far = 4, max_ending_here = 3

5. i=4, arr[4] = -2

• max_ending_here = 3 + (-2) = 1
• max_so_far remains 4 (since 1 < 4)
• max_ending_here is positive → keep as 1
• State: max_so_far = 4, max_ending_here = 1

6. i=5, arr[5] = 1

• max_ending_here = 1 + 1 = 2
• max_so_far remains 4 (since 2 < 4)
• max_ending_here is positive → keep as 2
• State: max_so_far = 4, max_ending_here = 2

7. i=6, arr[6] = 5

• max_ending_here = 2 + 5 = 7
• max_so_far updates from 4 to 7
• max_ending_here is positive → keep as 7
• State: max_so_far = 7, max_ending_here = 7

8. i=7, arr[7] = -3

• max_ending_here = 7 + (-3) = 4
• max_so_far remains 7 (since 4 < 7)
• max_ending_here is positive → keep as 4
• Final State: max_so_far = 7, max_ending_here = 4

Result: Maximum subarray sum = 7 (from subarray [4, -1, -2, 1, 5])

Code

#include <iostream>
#include <limits.h> // INT_MIN ke liye
using namespace std;

int kadane(int arr[], int n) {
    int max_ending_here = 0;  // current subarray sum
    int max_so_far = INT_MIN; // overall maximum sum
    
    for(int i=0; i<n; i++) {
        // current element ko add karo
        max_ending_here += arr[i];
        
        // agar yeh naya maximum hai toh update karo
        if(max_ending_here > max_so_far) {
            max_so_far = max_ending_here;
        }
        
        // agar sum negative hua, toh discard karo
        if(max_ending_here < 0) {
            max_ending_here = 0;
        }
    }
    
    return max_so_far;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Maximum contiguous sum is: " << kadane(arr, n);
    
    return 0;
}

Code Explanation:

1. Initialization:

• max_ending_here tracks current subarray sum (start with 0)
• max_so_far stores overall maximum (start with INT_MIN)

1. Loop Through Array:

• Har element ko max_ending_here  mein add karo
• Agar max_ending_here >  max_so_far, toh naya maximum mil gaya
• Agar max_ending_here negative ho, toh naye subarray ka start karo (reset to 0)

1. Return Result:

• max_so_far mein final answer stored hai

Time Complexity Analysis

• Time Complexity: O(n) - ek hi baar array traverse kiya
• Space Complexity: O(1) - constant extra space use kiya

Practice it Yourself:

1. Rotate an array by K positions.
2. Find second largest element.
3. Check if array is sorted or not.
4. Find peak element (element which is greater than both neighbors).
5. Count number of elements greater than average.