Day 7 – Max Element, Second Largest/Smallest, Array Rules, Sorted/Rotated Check, and LeetCode Practice

Today I covered multiple core concepts related to arrays, including max/min finding techniques, array rules, checking for sortedness, removing duplicates, and solving LeetCode problems using both brute and optimal approaches.

---

Finding Maximum Element

1. Brute Force – Two Loops

int getMaxBrute(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        bool isMax = true;
        for (int j = 0; j < n; j++) {
            if (a[j] > a[i]) {
                isMax = false;
                break;
            }
        }
        if (isMax) return a[i];
    }
    return -1;
}
// TC: O(n²), SC: O(1)

---

2. Optimal – Linear Scan

int getMax(vector<int>& a) {
    int maxVal = INT_MIN;
    for (int i : a)
        if (i > maxVal) maxVal = i;
    return maxVal;
}
// TC: O(n), SC: O(1)

---

3. STL Method – *max_element

#include <algorithm>
int maxVal = *max_element(a.begin(), a.end());
// TC: O(n), SC: O(1)

---

4. Recursive

int getMaxRec(vector<int>& a, int n) {
    if (n == 1) return a[0];
    return max(a[n-1], getMaxRec(a, n-1));
}
// TC: O(n), SC: O(n) (recursion stack)

---

Array Rules and Properties

• Arrays can only hold one data type.

• Declaring an array globally (outside main) initializes all elements to 0.

• Arrays inside main() are not auto-initialized (contain garbage).

• Array max size:

  • Global: 10^7 (int)

  • Inside main: 10^6 (int)

• Access by address (e.g., a) gives base pointer — must access via index (a[i]).

• break: exits current loop only.

• return: exits current function entirely.

---

Second Largest and Second Smallest Elements

1. Brute Force – Sort and pick

sort(a.begin(), a.end());
int n = a.size();
int largest = a[n-1], second = -1;
for (int i = n-2; i >= 0; i--) {
    if (a[i] != largest) {
        second = a[i];
        break;
    }
}
// TC: O(n log n), SC: O(1)

---

2. Better – Linear Search after Sorting

void getElements(int arr[],int n)
{
    if(n==0 || n==1)
        cout<<-1<<" "<<-1<<endl;  // edge case when only one element is present in array
    int small=INT_MAX,second_small=INT_MAX;
    int large=INT_MIN,second_large=INT_MIN;
    int i;
    for(i=0;i<n;i++)
    {
        small=min(small,arr[i]);
        large=max(large,arr[i]);
    }
    for(i=0;i<n;i++)
    {
        if(arr[i]<second_small && arr[i]!=small)
            second_small=arr[i];
        if(arr[i]>second_large && arr[i]!=large)
            second_large=arr[i];
    }

    cout<<"Second smallest is "<<second_small<<endl;
    cout<<"Second largest is "<<second_large<<endl;
}
// TC: O(n), SC: O(1)

---

3. Best – One Pass

int largest = INT_MIN, second = INT_MIN;
for (int i : a) {
    if (i > largest) {
        second = largest;
        largest = i;
    } else if (i > second && i != largest) {
        second = i;
    }
}
// TC: O(n), SC: O(1)

Same logic applies for second smallest using INT_MAX and comparison in reverse.

---

Checking if Array is Sorted (Non-Decreasing)

1. Brute Force – Two Loops

bool isSortedBrute(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (a[j] < a[i]) return false;
    return true;
}
// TC: O(n²), SC: O(1)

---

2. Optimal – One Loop

bool isSorted(vector<int>& a) {
    for (int i = 1; i < a.size(); i++)
        if (a[i] < a[i-1]) return false;
    return true;
}
// TC: O(n), SC: O(1)

---

Removing Duplicates from Sorted Array – LeetCode 26

Brute Force – Using Set

set<int> s;
for (int x : nums) s.insert(x);

int idx = 0;
for (int x : s) nums[idx++] = x;
// TC: O(n + n log n), SC: O(n)

Set elements are stored in BST, so cannot access by index, use for-each.

---

Optimal – Two Pointers

int removeDuplicates(vector<int>& nums) {
    int i = 0;
    for (int j = 1; j < nums.size(); j++) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}
// TC: O(n), SC: O(1)

---

Check If Array Is Sorted and Rotated – LeetCode 1752

Idea:

• Count how many times current element > next element

• Must be ≤ 1 for rotated sorted array

• Check wraparound: (i+1)%n

bool check(vector<int>& nums) {
    int count = 0, n = nums.size();
    for (int i = 0; i < n; i++) {
        if (nums[i] > nums[(i+1)%n])
            count++;
    }
    return count <= 1;
}
// TC: O(n), SC: O(1)

---

Rotate Array – LeetCode 189

Brute Force (TLE)

// Rotate by 1, k times (TLE)
for (int i = 0; i < k; i++) {
    int last = nums.back();
    for (int j = nums.size()-1; j > 0; j--)
        nums[j] = nums[j-1];
    nums[0] = last;
}
// TC: O(k*n), SC: O(1)

---

Optimal – Reverse Method

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}
// TC: O(n), SC: O(1)

First medium problem I solved without help. Felt good to apply logic step-by-step.

---

Summary:

• Covered multiple techniques to find max/second max/min

• Learned key rules about arrays, scope, and behavior in C++

• Revisited sortedness checking and duplicate removal

• Solved multiple LeetCode problems using both brute and optimal approaches

• Getting comfortable with array logic and edge cases