Mastering Array Fundamentals: Finding the Second Largest Element, Checking Sorted Arrays, and In-Place Duplicate Removal

This chapter introduces the fundamental concepts of arrays, including their memory layout, declaration limits, and initialization behaviors. It then walks through a series of progressively challenging problems—finding the largest and second largest elements, verifying if an array is sorted, and removing duplicates in-place—using a structured "Brute-Better-Optimal" framework designed to excel in technical interviews.

1. Introduction to Arrays: Definition, Syntax, and Memory Layout

An array is a fundamental linear data structure that stores a collection of homogeneous (similar) elements in contiguous memory locations.

Core Characteristics of Arrays

• Homogeneity: An array can only store elements of the same data type. For instance, an integer array can only store integers, a character array can only store characters, and a string array can only store strings. It cannot contain a mix of different types (e.g., an integer and a string together).
• Contiguous Memory Allocation: When an array is declared, the operating system allocates a continuous block of memory.
• Index-Based Access: Because memory is contiguous, any element can be accessed in $O(1)$ constant time using its index. Array indexing is zero-based, meaning the first element is at index 0 and the last element is at index N - 1 (where N is the size of the array).

Syntax and Declaration

The syntax for declaring an array varies across programming languages:

C++ Declaration

int arr[6]; // Declares an array of size 6 containing garbage values

Java Declaration

int[] arr = new int[6]; // Declares an array of size 6 initialized to default values (0)

Memory Representation Workflow

When an array is declared, the computer allocates a block of memory starting at a random base address $X$. Although we cannot predict the exact value of $X$, we can guarantee that successive elements are stored at predictable offsets based on the size of the data type.

Note: Because we cannot predict the base address $X$ before runtime, we cannot access array elements directly via raw memory addresses. Instead, we use zero-based indexing (0 to N-1), which the compiler internally translates into memory offsets.

2. Memory Allocation Limits: Local vs. Global Declarations

The location where you declare an array inside your program significantly impacts both its maximum permissible size and its default initial values.

Local Declaration (Inside main or a Function)

• Storage Location: Allocated on the Stack segment of memory.
• Initialization: Elements are filled with garbage values (unpredictable data left over in memory).
• Maximum Size Limit: Typically restricted to approximately $10^6$ elements for an integer array. Exceeding this limit will trigger a Stack Overflow error.

Global Declaration (Outside any Function)

• Storage Location: Allocated on the Data Segment (or BSS segment) of memory.
• Initialization: Elements are automatically initialized to zero (0) in C++ and Java.
• Maximum Size Limit: Typically extends up to approximately $10^7$ elements for an integer array.

Summary of Declaration Behaviors

3. Problem 1: Finding the Largest Element in an Array

Problem Statement

Given an array of integers, find and return the largest element in the array.

Brute Force Approach: Sorting

The most intuitive way to find the largest element is to sort the array in ascending order. Once sorted, the largest element will naturally reside at the very last index (N - 1).

Algorithm

1. Sort the array using an efficient sorting algorithm (e.g., Merge Sort or Quick Sort).
2. Return the element at index N - 1.

C++ Implementation

#include <vector>
#include <algorithm>

int findLargestBrute(std::vector<int>& arr) {
    std::sort(arr.begin(), arr.end());
    return arr[arr.size() - 1];
}

Complexity Analysis

• Time Complexity: $O(N \log N)$ due to the sorting operation.
• Space Complexity: $O(1)$ auxiliary space (ignoring the recursive stack space used by the sorting algorithm).

Optimal Approach: Single-Pass Scan

Instead of sorting the entire array, we can maintain a tracking variable largest and update it as we traverse the array.

Real-Life Analogy

Imagine you are looking at a line of students to find the tallest one. You assume the first student is the tallest. As you walk down the line, if you see anyone taller than your current choice, you update your mental record. By the time you reach the end of the line, you have identified the tallest student.

Algorithm

1. Initialize a variable largest with the first element of the array: largest = arr[0].
2. Loop through the array from index 1 to N - 1.
3. If the current element arr[i] is greater than largest, update largest = arr[i].
4. Return largest.

C++ Implementation

#include <vector>

int findLargestOptimal(const std::vector<int>& arr) {
    int largest = arr[0];
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] > largest) {
            largest = arr[i];
        }
    }
    return largest;
}

Complexity Analysis

• Time Complexity: $O(N)$ because we traverse the array exactly once.
• Space Complexity: $O(1)$ auxiliary space as we only use a single variable.

4. Interview Strategy: The "Brute-Better-Optimal" Framework

When answering questions in a technical interview, jumping straight to the most optimal solution can sometimes work against you. Interviewers want to evaluate your problem-solving process, communication skills, and ability to optimize code systematically.

Why You Should Drive the Interview

1. Demonstrates Structured Thinking: Showing how you optimize a naive $O(N \log N)$ solution to an $O(N)$ solution highlights your understanding of algorithmic trade-offs.
2. Builds Rapport: Discussing edge cases and test cases before writing code ensures you and the interviewer are aligned.
3. Saves Time on Misunderstandings: If you misunderstand the problem, presenting a brute-force approach first gives the interviewer an early opportunity to correct your direction before you write complex code.

5. Problem 2: Finding the Second Largest Element (Brute Force & Better)

Problem Statement

Given an array of integers, find the second largest element in the array without using sorting. If no such element exists (e.g., all elements are identical), return -1 (or a minimum value representing non-existence).

Brute Force Approach: Sort and Backward Scan

If we sort the array in ascending order, the largest element is at arr[N - 1]. However, we cannot simply return arr[N - 2] because the array might contain duplicate values of the largest element.

Algorithm

1. Sort the array in ascending order.
2. Store the largest element: largest = arr[N - 1].
3. Traverse backward from index N - 2 down to 0.
4. The first element arr[i] that is not equal to largest is our second largest element.
5. If the loop finishes and no such element is found, it means all elements in the array are identical. Return -1.

C++ Implementation

#include <vector>
#include <algorithm>

int findSecondLargestBrute(std::vector<int>& arr) {
    int n = arr.size();
    if (n < 2) return -1;
    
    std::sort(arr.begin(), arr.end());
    int largest = arr[n - 1];
    
    for (int i = n - 2; i >= 0; --i) {
        if (arr[i] != largest) {
            return arr[i];
        }
    }
    return -1;
}

Complexity Analysis

• Time Complexity: $O(N \log N)$ for sorting + $O(N)$ for the backward scan in the worst case. Overall: $O(N \log N)$.
• Space Complexity: $O(1)$ auxiliary space.

Better Approach: Two-Pass Scan

We can eliminate the $O(N \log N)$ sorting step by using two sequential linear scans.

Algorithm

1. First Pass: Find the largest element in the array (similar to Problem 1). Let this be largest.
2. Initialize second_largest = -1 (or INT_MIN if the array can contain negative numbers).
3. Second Pass: Traverse the array again. For each element arr[i]:
   • If arr[i] is greater than second_largest AND arr[i] is not equal to largest, update second_largest = arr[i].
4. Return second_largest.

C++ Implementation

#include <vector>
#include <climits>

int findSecondLargestBetter(const std::vector<int>& arr) {
    int n = arr.size();
    if (n < 2) return -1;

    int largest = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (arr[i] > largest) {
            largest = arr[i];
        }
    }

    int second_largest = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (arr[i] > second_largest && arr[i] != largest) {
            second_largest = arr[i];
        }
    }

    return (second_largest == INT_MIN) ? -1 : second_largest;
}

Complexity Analysis

• Time Complexity: $O(N) + O(N) = O(2N)$, which simplifies to $O(N)$.
• Space Complexity: $O(1)$ auxiliary space.

6. Problem 2 (Cont.): Single-Pass Optimal Approach for Second Largest & Second Smallest

To achieve the absolute optimal solution, we can find both the largest and second largest elements in a single pass ($O(N)$ time with only one traversal).

Single-Pass Logic

As we traverse the array, we compare each element arr[i] with our current largest and second_largest values:

• Case 1: If arr[i] > largest, the current largest becomes the new second_largest, and arr[i] becomes the new largest.
• Case 2: If arr[i] < largest but arr[i] > second_largest, we update only second_largest to be arr[i].
• Case 3: If arr[i] == largest or arr[i] <= second_largest, we do nothing.

Real-Life Analogy

Think of a leaderboard. If a new player enters and scores higher than the 1st place player, the old 1st place player drops down to 2nd place, and the new player takes 1st. If the new player scores less than 1st place but higher than 2nd place, they simply take over 2nd place.

Complete Implementation: Second Largest & Second Smallest

Below is the complete, production-grade C++ implementation that calculates both the second largest and second smallest elements in an array in a single pass.

#include <vector>
#include <climits>
#include <iostream>

// Helper function to find the second largest element in a single pass
int getSecondLargest(const std::vector<int>& arr, int n) {
    int largest = arr[0];
    int second_largest = INT_MIN;

    for (int i = 1; i < n; ++i) {
        if (arr[i] > largest) {
            second_largest = largest;
            largest = arr[i];
        } else if (arr[i] < largest && arr[i] > second_largest) {
            second_largest = arr[i];
        }
    }
    return second_largest;
}

// Helper function to find the second smallest element in a single pass
int getSecondSmallest(const std::vector<int>& arr, int n) {
    int smallest = arr[0];
    int second_smallest = INT_MAX;

    for (int i = 1; i < n; ++i) {
        if (arr[i] < smallest) {
            second_smallest = smallest;
            smallest = arr[i];
        } else if (arr[i] > smallest && arr[i] < second_smallest) {
            second_smallest = arr[i];
        }
    }
    return second_smallest;
}

// Main function returning both values
std::pair<int, int> getSecondOrderElements(std::vector<int>& arr) {
    int n = arr.size();
    if (n < 2) return {-1, -1};

    int sLargest = getSecondLargest(arr, n);
    int sSmallest = getSecondSmallest(arr, n);

    return {sLargest, sSmallest};
}

Complexity Analysis

• Time Complexity: $O(N)$ since we perform a single pass over the array of size $N$.
• Space Complexity: $O(1)$ auxiliary space.

7. Problem 3: Checking if an Array is Sorted (Non-Descending Order)

Problem Statement

Given an array of size N, check if the array is sorted in non-descending (ascending) order. Return true if sorted, and false otherwise.

An array is sorted in non-descending order if, for every index i (from 1 to N - 1):

Optimal Approach: Single-Pass Adjacent Comparison

We do not need any complex algorithms here. A single linear scan comparing each element with its immediate predecessor is sufficient.

Algorithm

1. Start a loop from index 1 to N - 1.
2. For each index i, check if arr[i] < arr[i - 1].
3. If this condition is met, the array is out of order. Immediately return false.
4. If the loop completes without returning false, return true.

C++ Implementation

#include <vector>

bool isSorted(const std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[i - 1]) {
            return false; // Found an unsorted pair
        }
    }
    return true; // Entire array is sorted
}

Complexity Analysis

• Time Complexity: $O(N)$ in the worst case (when the array is sorted or the unsorted element is at the end).
• Space Complexity: $O(1)$ auxiliary space.

8. Problem 4: Removing Duplicates from a Sorted Array (Brute Force Set Approach)

Problem Statement

Given a sorted array of integers, remove the duplicate elements in-place such that each unique element appears only once at the beginning of the array. The relative order of the elements must be kept the same.

You must return the number of unique elements, say K. The first K elements of the modified array must hold the unique values. The remaining elements do not matter.

Brute Force Approach: Using a Set

A std::set in C++ (or HashSet/LinkedHashSet in Java) inherently stores only unique elements. Since the input array is already sorted, we can leverage a set to filter out duplicates and then write them back to the array.

Algorithm

1. Declare a set data structure.
2. Iterate through the array and insert every element into the set.
3. Retrieve the unique elements from the set and overwrite the first K positions of the original array (where K is the size of the set).
4. Return the size of the set (K).

C++ Implementation

#include <vector>
#include <set>

int removeDuplicatesBrute(std::vector<int>& arr) {
    std::set<int> unique_elements;
    
    // Step 1: Insert all elements into the set
    for (int num : arr) {
        unique_elements.insert(num);
    }
    
    // Step 2: Copy unique elements back to the beginning of the array
    int index = 0;
    for (int num : unique_elements) {
        arr[index++] = num;
    }
    
    return unique_elements.size();
}

Complexity Analysis

• Time Complexity: $O(N \log N)$ because inserting an element into a balanced BST-based set takes $O(\log N)$ time, and we do this $N$ times. Copying elements back takes $O(N)$ time.
• Space Complexity: $O(N)$ auxiliary space to store the unique elements in the set in the worst case (when all elements are unique).

9. Problem 4 (Cont.): Two-Pointer In-Place Optimal Approach for Duplicate Removal

To satisfy the in-place constraint optimally without using extra memory, we can use a two-pointer approach.

Two-Pointer Logic

Since the array is sorted, all duplicate elements are grouped together. We can maintain two pointers:

• i: Points to the last known unique element.
• j: Scans ahead to find the next unique element.

Initial State:
[ 1,  1,  2,  2,  2,  3,  3 ]
  ^   ^
  i   j   (arr[j] == arr[i], so increment j)

j moves to index 2:
[ 1,  1,  2,  2,  2,  3,  3 ]
  ^       ^
  i       j   (arr[j] != arr[i], increment i, copy arr[j] to arr[i])

After copy:
[ 1,  2,  2,  2,  2,  3,  3 ]
      ^   ^
      i   j   (increment j until arr[j] != arr[i])

j moves to index 5:
[ 1,  2,  2,  2,  2,  3,  3 ]
      ^               ^
      i               j   (arr[j] != arr[i], increment i, copy arr[j] to arr[i])

After copy:
[ 1,  2,  3,  2,  2,  3,  3 ]
          ^           ^
          i           j

Step-by-Step Dry Run

Let's trace the algorithm with the array: arr = [1, 1, 2, 2, 3]

1. Initialization: i = 0. The first element arr[0] = 1 is always unique.
2. Iteration j = 1: arr[1] is 1. Since arr[j] == arr[i] (1 == 1), we do nothing.
3. Iteration j = 2: arr[2] is 2. Since arr[j] != arr[i] (2 != 1):
   • Increment i to 1.
   • Set arr[i] = arr[j] $\rightarrow$ arr[1] = 2.
   • Array state: [1, 2, 2, 2, 3]
4. Iteration j = 3: arr[3] is 2. Since arr[j] == arr[i] (2 == 2), we do nothing.
5. Iteration j = 4: arr[4] is 3. Since arr[j] != arr[i] (3 != 2):
   • Increment i to 2.
   • Set arr[i] = arr[j] $\rightarrow$ arr[2] = 3.
   • Array state: [1, 2, 3, 2, 3]
6. End of Loop: Return i + 1 (which is 3). The first 3 elements [1, 2, 3] are the unique elements.

C++ Implementation

#include <vector>

int removeDuplicatesOptimal(std::vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return 0;
    
    int i = 0; // Pointer to the last unique element
    for (int j = 1; j < n; ++j) {
        if (arr[j] != arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1; // Number of unique elements
}

Complexity Analysis

• Time Complexity: $O(N)$ because we traverse the array of size $N$ exactly once.
• Space Complexity: $O(1)$ auxiliary space as we modify the array in-place without using extra data structures.

10. Comparative Analysis of Algorithms & Complexities

The table below summarizes the algorithms covered in this chapter, comparing their approaches, time complexities, and space complexities.

11. Summary and Key Takeaways

• Contiguous Memory Layout: Arrays are stored in contiguous memory blocks. While the base address $X$ is random and unpredictable, the offset of any index i is always $X + i \times \text{element\_size}$, enabling $O(1)$ random access.
• Stack vs. Data Segment Limits: Arrays declared locally inside functions are stored on the stack (limited to $\approx 10^6$ elements and initialized with garbage values). Globally declared arrays are stored in the data segment (allowing up to $\approx 10^7$ elements and auto-initialized to 0).
• The Interview Progression: Always present your solutions in a Brute $\rightarrow$ Better $\rightarrow$ Optimal sequence. This structure demonstrates your analytical depth and keeps the interviewer engaged.
• Single-Pass Optimization: Finding the second largest element can be optimized from a two-pass $O(2N)$ approach to a single-pass $O(N)$ approach by updating the second largest value whenever a new largest value is found.
• In-Place Array Modification: The two-pointer technique is a powerful pattern for in-place array manipulation. By maintaining a write pointer i and a read pointer j, you can filter, reorder, or modify elements in $O(N)$ time and $O(1)$ space.