DEV Community: Mahbub Alam Masum

How to Find the Element that Appears Once in an Array

Mahbub Alam Masum — Mon, 24 Jun 2024 09:50:47 +0000

Finding the element that appears only once in an array where all other elements appear twice is a common problem in coding interviews and programming challenges. In this article, we'll discuss four approaches to solve this problem: one using a brute force approach, another using hashing, a third using a map, and the optimal approach using XOR.

Solution 1: Brute Force Approach (using Nested Loop)

This method involves using a nested loop to find the element that appears only once.

Implementation:

// Solution-1: Brute Force Approach (using Nested Loop)
// Time Complexity: O(n*n)
// Space Complexity: O(1)
int getSingleElement(vector<int> &arr, int n)
{
    // Loop for selecting elements
    for (int i = 0; i < n; i++)
    {
        // Selected element
        int num = arr[i];

        int counter = 0;

        // Find the occurrence using Linear Search
        for (int j = 0; j < n; j++)
        {
            if (arr[j] == num)
            {
                counter++;
            }
        }

        // If the occurrence is 1, return that element
        if (counter == 1)
        {
            return num;
        }
    }

    // In case no element appears once
    return -1;
}

Logic:

1. Nested Loop: Use an outer loop to iterate through each element of the array. Use an inner loop to count the occurrences of the selected element.

2. Check for Single Occurrence: If the count of the selected element is 1, return that element.

Time Complexity: O(n*n)

Explanation: Each element in the array is compared with every other element, resulting in a nested loop.

Space Complexity: O(1)

Explanation: No additional space is used apart from variables for counting.

Example:

Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.

Solution 2: Better Approach (using Hashing)

This method uses hashing to find the element that appears only once.

Implementation:

// Solution-2: Better Approach 1 (using Hashing)
// Time Complexity: O(3n) ~ O(n)
// Space Complexity: O(maxElement+1)
int getSingleElement(vector<int> &arr, int n)
{
    // Find the maximum element
    int maxElement = arr[0];
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > maxElement)
        {
            maxElement = arr[i];
        }
    }

    // Hash Array of size maxElement + 1
    vector<int> hash(maxElement + 1, 0);

    // Hash the array
    for (int i = 0; i < n; i++)
    {
        hash[arr[i]]++;
    }

    // Find the single element and return that
    for (int i = 0; i < n; i++)
    {
        if (hash[arr[i]] == 1)
        {
            return arr[i];
        }
    }

    // In case no element appears once
    return -1;
}

Logic:

1. Find Maximum Element: Traverse the array to find the maximum element.

2. Hash the Array: Create a hash array of size maxElement + 1 and count the occurrences of each element. maxElement is the maximum element in the array.

3. Check for Single Occurrence: Traverse the hash array to find the element with a count of 1.

Time Complexity: O(3n) ~ O(n)

Explanation: The array is traversed three times (to find the maximum element, hash the array, and find the single element).

Space Complexity: O(maxElement+1)

Explanation: Additional space is used for the hash array. Here, maxElement is the maximum element in the array.

Example:

Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.

Solution 3: Better Approach (using Map for Hashing)

This method uses a map to find the element that appears only once.

Implementation:

// Solution-3: Better Approach 2 (using Map for Hashing)
// Time Complexity: O(n * log M) + O(M)
// Space Complexity: O(M)
int getSingleElement(vector<int> &arr, int n)
{
    // Declare the Map
    map<int, int> track;

    // Hash the array
    for (int i = 0; i < n; i++)
    {
        track[arr[i]]++;
    }

    // Find the single element and return that
    for (auto it : track)
    {
        if (it.second == 1)
        {
            return it.first;
        }
    }

    // In case no element appears once
    return -1;
}

Logic:

1. Hash the Array: Use a map to count the occurrences of each element.

2. Check for Single Occurrence: Traverse the map to find the element with a count of 1.

Time Complexity: O(n * log M) + O(M)

Explanation: The array is hashed in O(n * log M) time and then traversed in O(M) time. Here, M is the size of the map (in this case, M = (n/2)+1) and n = size of the array. Note: [ It takes O(log M) time to access an element in the map ]

Space Complexity: O(M)

Explanation: Additional space is used for the map. Here, M is the size of the map (in this case, M = (n/2)+1) and n = size of the array.

Example:

Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.

Solution 4: Optimal Approach (using XOR)

This method uses XOR to find the element that appears only once.

Implementation:

// Solution-4: Optimal Approach (using XOR)
// Time Complexity: O(n)
// Space Complexity: O(1)
int getSingleElement(vector<int> &arr, int n)
{
    int appearsOnce = 0;

    // XOR all the elements
    for (int i = 0; i < n; i++)
    {
        appearsOnce ^= arr[i];
    }

    return appearsOnce;
}

Logic:

1. XOR All Elements: XOR all the elements of the array. The elements appearing twice will cancel out, leaving the element that appears once. This approach leverages the property a ^ a = 0 and a ^ 0 = a.

Time Complexity: O(n)

Explanation: The array is traversed once.

Space Complexity: O(1)

Explanation: No additional space is used.

Example:

Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.

Comparison

Brute Force Approach:
- Pros: Simple and straightforward.
- Cons: Inefficient for large arrays due to O(n*n) time complexity.
Better Approach (using Hashing):
- Pros: More efficient than brute force with O(3n) ~ O(n) time complexity.
- Cons: Requires additional space for the hash array.
Better Approach (using Map for Hashing):
- Pros: Efficient with O(n * log M) + O(M) time complexity.
- Cons: Requires additional space for the map for hashing.
Optimal Approach (using XOR):
- Pros: Highly efficient with O(n) time complexity and no additional space usage.
- Cons: Slightly more complex to understand but very efficient.

Edge Cases

Empty Array: Returns -1 as there are no elements to check.
No Single Element: Returns -1 if no element appears exactly once.
All Elements are the Same: Returns -1 if no unique element exists.

Additional Notes

Efficiency: The XOR technique is the most time-efficient and space-efficient, making it preferable for large arrays.
Practicality: The choice of approach depends on the specific constraints and requirements of the problem, such as array size and available memory.

Conclusion

Finding the element that appears once in an array where all other elements appear twice can be efficiently achieved using various approaches. The optimal choice depends on the specific constraints and requirements of the problem, with the XOR method being the most efficient in terms of both time and space.

How to Find the Maximum Consecutive Ones in an Array

Mahbub Alam Masum — Sat, 22 Jun 2024 09:07:16 +0000

Finding the maximum number of consecutive 1's in a binary array is a common problem that can be efficiently solved with a linear time algorithm. In this article, we will discuss an optimal approach to solve this problem.

Solution: Optimal Approach

This approach scans through the array once, keeping track of the current streak of consecutive 1's and updating the maximum streak encountered.

Implementation:

// Solution: Optimal Approach
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMaxConsecutiveOnes(vector<int> &arr, int n)
{
    int maxOnes = 0;
    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 1)
        {
            count++;

            if (count > maxOnes)
            {
                maxOnes = count;
            }
        }
        else
        {
            count = 0;
        }
    }

    return maxOnes;
}

Logic:

1. Initialize Counters: Use the maxOnes variable to store the maximum number of consecutive 1's found and count to store the current number of consecutive 1's.

2. Traverse the Array: Iterate through each element in the array. If the element is 1, increment count and update maxOnes if count exceeds maxOnes. If the element is not 1, reset count to 0.

3. Return Result: After the loop ends, return maxOnes as the result.

Time Complexity: O(n)

Explanation: The array is traversed once, resulting in a linear time complexity.

Space Complexity: O(1)

Explanation: The algorithm uses a constant amount of extra space for the counters.

Example:

Input: arr = [1, 1, 0, 1, 1, 1]
Output: 3
Explanation: The maximum number of consecutive 1's is 3.

Edge Cases

Empty Array: If the input array is empty, the function should return 0 as there are no elements.
Array with No 1's: If the array contains only 0's, the function should return 0 as there are no 1's.
Array with No 0's: If the array contains only 1's, the function should return the length of the array as all elements are consecutive 1's.
Single Element Array: If the array contains only one element, which could be either 0 or 1. Then the function should return 0 if the element is 0 and 1 if the element is 1.

Additional Notes

Efficiency: This approach is optimal with a time complexity of O(n) and space complexity of O(1), making it suitable for large arrays.
Practicality: The algorithm is straightforward and easy to implement, making it a practical choice for solving this problem in real-world scenarios.

Conclusion

Finding the maximum number of consecutive 1's in a binary array can be efficiently solved using a linear scan approach. This method ensures optimal performance with minimal space usage, making it a robust solution for various applications.

How to Find the Missing Number in an Array

Mahbub Alam Masum — Fri, 21 Jun 2024 16:09:40 +0000

In an array containing numbers from 1 to N, where one number is missing, the goal is to find the missing number. Here, we'll discuss four different methods to achieve this, ranging from brute force to optimal approaches.

Solution 1: Brute Force Approach (Using Nested Loop & Linear Search)

This approach involves checking for each number from 1 to N whether it exists in the array.

Implementation:

// Solution-1: Brute Force Approach (using Nested Loop & Linear Search)
// Time Complexity: O(n*n)
// Space Complexity: O(1)
int findMissingNumber(vector<int> &arr, int n)
{
    // Outer loop that runs from 1 to N
    for (int i = 1; i <= n; i++)
    {
        // `flag` variable to check if an element exists
        bool flag = false;

        // Search the element using Linear Search
        for (int j = 0; j < n - 1; j++)
        {
            if (arr[j] == i)
            {
                flag = true;
                break;
            }
        }

        // Check if the element is missing
        if (!flag)
        {
            return i;
        }
    }

    // If loop completes without finding a missing number (shouldn't happen)
    // It is just to avoid warnings.
    return -1;
}

Logic:

Outer Loop: Iterate through numbers from 1 to N.
Linear Search: For each number, check if it exists in the array using a nested loop.
Flag Check: Use a flag to indicate if the number was found. If not, return the number as it is the missing one.

Time Complexity: O(n²)

Explanation: The outer loop runs from 1 to N and for each iteration of the outer loop, the inner loop runs up to N-1. This results in a time complexity of O(n * (n-1)), which simplifies to O(n²).

Space Complexity: O(1)

Explanation: Only a few additional variables (like flag) are used, which do not depend on the size of the input array.

Example:

Input: arr = [1, 2, 4, 6, 3, 7, 8], n = 8
Output: 5
Explanation: The number 5 is missing from the array.

Solution 2: Better Approach (Using Hashing)

This approach uses a hash table to track the presence of numbers in the array.

Implementation:

// Solution-2: Better Approach (using Hashing)
// Time Complexity: O(n) + O(n) ~ O(2n)
// Space Complexity: O(n)
int findMissingNumber(vector<int> &arr, int n)
{
    // Hash table to store the presence of numbers
    vector<int> hash(n + 1, 0);

    // Mark the presence of elements in the hash table
    for (int i = 0; i < n - 1; i++)
    {
        hash[arr[i]] = 1;
    }

    // Find the missing number by iterating through the hash table
    for (int i = 1; i <= n; i++)
    {
        if (hash[i] == 0)
        {
            return i;
        }
    }

    // If loop completes without finding a missing number (shouldn't happen)
    // It is just to avoid warnings.
    return -1;
}

Logic:

Initialize Hash Table: Create a hash table to track numbers from 1 to N.
Mark Presence: Iterate through the array, marking the presence of each number in the hash table.
Find Missing Number: Iterate through the hash table to find the number that is not marked.

Time Complexity: O(n)

Explanation: The first loop runs through the array of size N-1 to populate the hash table and the second loop runs through the hash table of size N to find the missing number. Thus, the overall time complexity is O(n) + O(n-1), which simplifies to O(n).

Space Complexity: O(n)

Explanation: An additional hash table of size N is used to keep track of the presence of each number.

Example:

Input: arr = [1, 2, 4, 6, 3, 7, 8], n = 8
Output: 5
Explanation: The number 5 is not present in the hash table.

Solution 3: Optimal Approach 1 (Summation Approach)

This approach uses the sum formula for the first N natural numbers to find the missing number.

Implementation:

// Solution-3: Optimal Approach 1 (Summation Approach)
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMissingNumber(vector<int> &arr, int n)
{
    // Sum of all numbers from 1 to N
    int sumOfNNums = (n * (n + 1)) / 2;

    int sumOfArr = 0;

    // Calculate the actual sum of elements in the array
    for (int i = 0; i < n - 1; i++)
    {
        sumOfArr += arr[i];
    }

    int missingNum = sumOfNNums - sumOfArr;

    return missingNum;
}

Logic:

Sum of N Numbers: Calculate the sum of numbers from 1 to N using the formula sum = (n * (n + 1)) / 2.
Sum of Array: Calculate the sum of elements in the array.
Find Missing Number: Subtract the sum of the array from the sum of N numbers to get the missing number.

Time Complexity: O(n)

Explanation: The loop runs through the array once to calculate the sum of the elements, resulting in a time complexity of O(n).

Space Complexity: O(1)

Explanation: Only a few additional variables (like sumOfNNums and sumOfArr) are used, which do not depend on the size of the input array.

Example:

Input: arr = [1, 2, 4, 6, 3, 7, 8], n = 8
Output: 5
Explanation: The sum of numbers from 1 to 8 is 36 and the sum of the array is 31. Thus, the missing number is 36 - 31 = 5.

Solution 4: Optimal Approach 2 (XOR Approach)

This approach uses the XOR operation to find the missing number efficiently.

Implementation:

// Solution-4: Optimal Approach 2 (XOR Approach)
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMissingNumber(vector<int> &arr, int n)
{
    int xor1 = 0;
    int xor2 = 0;

    for (int i = 0; i < n - 1; i++)
    {
        // XOR of array elements
        xor2 ^= arr[i];

        // XOR up to [1...N-1]
        xor1 ^= (i + 1);
    }

    // XOR up to [1...N]
    xor1 ^= n;

    // The missing number
    return xor1 ^ xor2;
}

Logic:

XOR Array Elements: Compute the XOR of all elements in the array.
XOR Up to N: Compute the XOR of all numbers from 1 to N.
Find Missing Number: XOR the results from steps 1 and 2. The result will be the missing number.

Time Complexity: O(n)

Explanation: The first loop runs through the array of size N-1 to calculate the XOR of the elements and the second loop runs up to N to calculate the XOR of the range from 1 to N. Thus, the overall time complexity is O(n-1) + O(n), which simplifies to O(n).

Space Complexity: O(1)

Explanation: Only a few additional variables (like xor1 and xor2) are used, which do not depend on the size of the input array.

Example:

Input: arr = [1, 2, 4, 6, 3, 7, 8], n = 8
Output: 5
Explanation: XOR of all array elements and XOR of numbers from 1 to 8 will result in the missing number, which is 5.

Comparison

Brute Force Approach:
- Pros: Simple and easy to understand.
- Cons: Inefficient with O(n²) time complexity.
Hashing Approach:
- Pros: More efficient with O(n) time complexity.
- Cons: Uses extra space for the hash table.
Summation Approach:
- Pros: Very efficient with O(n) time complexity and O(1) space complexity.
- Cons: Might face integer overflow for very large values of N.
XOR Approach:
- Pros: Efficient with O(n) time complexity and O(1) space complexity.
- Cons: Slightly more complex to understand compared to summation approach.

Edge Cases

Empty Array: If the input array is empty, the missing number should be 1.
Single Element Missing: When the array contains only one element, either 1 (missing 2) or 2 (missing 1), handle by checking and returning the missing number.
All Elements Present: If the array contains all elements from 1 to N without any missing number (should not happen if constraints guarantee a missing number), return a sentinel value like -1.
Duplicated Elements: This scenario is not considered because the problem constraints specify that all elements are distinct.

Additional Notes

Integer Overflow: For the summation approach, consider the risk of integer overflow when calculating the sum of the first N natural numbers. In practical implementations, ensure the language or environment can handle large integer values.
Data Types: Choose appropriate data types to handle the range of input values, especially for large N.
Performance Considerations: While the brute force approach is easy to implement, it is not suitable for large arrays due to its O(n²) time complexity. The hashing and XOR approaches are preferable for large datasets.
In-place Modifications: For space efficiency, the XOR approach modifies the input array in place. Ensure that this behavior is acceptable in the context of the problem or use case.
Understanding XOR: The XOR approach leverages the property that a ^ a = 0 and a ^ 0 = a. It effectively cancels out duplicate elements and isolates the missing number. This method is both efficient and elegant but requires understanding of bitwise operations.

Conclusion

Finding the missing number in an array of size N-1 can be achieved using various methods, from simple brute force to optimal XOR-based solutions. Depending on the constraints and requirements, one can choose the most suitable approach.

Intersection of Two Sorted Arrays

Mahbub Alam Masum — Thu, 20 Jun 2024 18:44:03 +0000

Finding the intersection of two sorted arrays is a common problem in coding interviews and programming challenges. In this article, we'll discuss two approaches to solve this problem: one using a brute force approach and another using two-pointers technique.

Solution 1: Brute Force Approach (using Nested Loop)

This method involves using a nested loop to find the intersection of two arrays.

Implementation:

// Solution-1: Brute Force Approach
// Time Complexity: O(m * n)
// Space Complexity: O(m)
vector<int> intersectionOfSortedArrays(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    vector<int> temp;
    vector<int> visited(m, 0);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // If element matches and has not been matched with any element before
            if (arr1[i] == arr2[j] && visited[j] == 0)
            {
                temp.push_back(arr2[j]);
                visited[j] = 1;
                break;
            }
            // As the array is sorted, element will not be beyond this
            else if (arr2[j] > arr1[i])
            {
                break;
            }
        }
    }

    return temp;
}

Logic:

1. Track Visited Elements:

Initialize a visited vector of size m (length of arr2) with all elements set to 0. This vector is used to track elements in arr2 that have already been matched.

2. Nested Loop:

Iterate through each element of arr1 using the outer loop. For each element in arr1, iterate through each element of arr2 using the inner loop.

3. Check for Matches:

If the current element of arr1 matches the current element of arr2 and the visited marker for that element in arr2 is 0 (indicating it has not been matched yet), add the element to the result vector temp and mark it as visited by setting the corresponding element in the visited vector to 1.
If the current element of arr2 is greater than the current element of arr1, break out of the inner loop as the arrays are sorted and no further match will be found for the current element of arr1.

Time Complexity: O(m * n)

Explanation: Each element in arr1 is compared with every element in arr2, resulting in a nested loop.

Space Complexity: O(m)

Explanation: Additional space is used to store the visited vector and the result vector temp.

Example:

Input: arr1 = [1, 2, 2, 3, 4], arr2 = [2, 2, 3, 5, 6]
Output: intersection = [2, 2, 3]
Explanation: Elements 2 and 3 are common in both arrays.

Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to find the intersection efficiently.

Implementation:

// Solution-2: Optimal Approach (Using Two Pointers)
// Time Complexity: O(m + n)
// Space Complexity: O(min(n, m))
vector<int> intersectionOfSortedArrays(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    int i = 0;
    int j = 0;
    vector<int> temp;

    while (i < n && j < m)
    {
        if (arr1[i] < arr2[j])
        {
            i++;
        }
        else if (arr1[i] > arr2[j])
        {
            j++;
        }
        else
        {
            temp.push_back(arr1[i]);
            i++;
            j++;
        }
    }

    return temp;
}

Logic:

1. Initialize Pointers:

Initialize two pointers i and j, both set to 0. These pointers will traverse arr1 and arr2, respectively.

2. Traverse Arrays:

Use a while loop to traverse both arrays as long as both pointers are within the bounds of their respective arrays.

3. Compare Elements:

If the current element of arr1 is less than the current element of arr2, increment pointer i to move to the next element in arr1.
If the current element of arr1 is greater than the current element of arr2, increment pointer j to move to the next element in arr2.
If the current elements of both arr1 and arr2 are equal, add the element to the result vector temp and increment both pointers i and j to move to the next elements in both arrays.

Time Complexity: O(m + n)

Explanation: Each array is traversed once using two pointers.

Space Complexity: O(min(n, m))

Explanation: The result vector temp stores the intersection elements, which can be up to the size of the smaller array.

Example:

Input: arr1 = [1, 2, 2, 3, 4], arr2 = [2, 2, 3, 5, 6]
Output: intersection = [2, 2, 3]
Explanation: Elements 2 and 3 are common in both arrays.

Comparison

Brute Force Approach:
- Pros: Simple and straightforward.
- Cons: Inefficient for large arrays due to O(m * n) time complexity and additional space usage.
Optimal Approach:
- Pros: Efficient with O(m + n) time complexity and lower space complexity.
- Cons: Slightly more complex to implement but highly efficient for large arrays.

Edge Cases

Empty Arrays: Returns an empty array as there are no elements to intersect.
No Intersection: Returns an empty array if there are no common elements.
Identical Arrays: Returns the entire array as all elements are common.

Additional Notes

Efficiency: The two-pointers technique is more time-efficient, making it preferable for large arrays.
Practicality: Both methods handle intersections efficiently but the choice depends on the size of the arrays and space constraints.

Conclusion

Finding the intersection of two sorted arrays can be efficiently achieved using either a brute force approach or a two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.

Union of Two Sorted Arrays

Mahbub Alam Masum — Wed, 19 Jun 2024 07:10:52 +0000

Finding the union of two sorted arrays involves combining the elements of both arrays without duplicates. This problem can be solved using different approaches, each with its own time and space complexity. In this article, we'll discuss two approaches to achieve this union.

Solution 1: Brute Force Approach (using Set)

This method involves using a set to store the unique elements from both arrays, ensuring that duplicates are removed.

Implementation:

// Solution-1: Brute Force Approach (Using Set)
// Time Complexity: O((m+n)log(m+n))
// Space Complexity: O(m+n)
// {If Space of temp Array is considered}
// Space Complexity: O(1)
// {If Space of temp Array is Not considered}
vector<int> unionOfSortedArrays1(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    set<int> uniqueElements;

    for (int i = 0; i < n; i++)
    {
        uniqueElements.insert(arr1[i]);
    }

    for (int i = 0; i < m; i++)
    {
        uniqueElements.insert(arr2[i]);
    }

    vector<int> temp;

    for (auto it : uniqueElements)
    {
        temp.push_back(it);
    }

    return temp;
}

Logic:

Insert Elements into Set: Insert all elements of both arrays into a set to remove duplicates.
Copy to Vector: Copy elements from the set back to a temporary vector.

Time Complexity: O((m+n) log(m+n))

Explanation: Inserting each element from arr1 and arr2 into the set uniqueElements takes O(log k) time, where k is the number of elements in the set. As we insert a total of m + n elements, this results in O((m+n) log(m+n)) time complexity. After inserting all elements, copying the set elements back to a vector takes O(m+n) time.

Space Complexity: O(m+n)

Explanation: The set uniqueElements can contain up to m + n elements in the worst case where there are no duplicates. Additionally, the temporary vector temp also stores up to m + n elements. If we consider the space required for the set and the temporary vector, the space complexity is O(m+n).

If we do not consider the temporary vector, the space complexity is O(1) as we are only using the set for extra storage.

Example:

Input: arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], n = 10, arr2 = [2, 3, 4, 4, 5, 11, 12], m = 7
Output: union = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Explanation: Elements from both arrays are combined without duplicates.

Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to efficiently merge the arrays while avoiding duplicates.

Implementation:

// Solution-2: Optimal Approach (Using 2 Pointers)
// Time Complexity: O(m+n)
// Space Complexity: O(m+n)
// {If Space of temp Array is considered}
// Space Complexity: O(1)
// {If Space of temp Array is Not considered}
vector<int> unionOfSortedArrays2(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    int i = 0;
    int j = 0;

    vector<int> temp;

    while (i < n && j < m)
    {
        if (arr1[i] <= arr2[j])
        {
            if (temp.size() == 0 || arr1[i] != temp.back()) // Avoid duplicates
            {
                temp.push_back(arr1[i]);
            }
            i++;
        }
        else
        {
            if (temp.size() == 0 || arr2[j] != temp.back()) // Avoid duplicates
            {
                temp.push_back(arr2[j]);
            }
            j++;
        }
    }

    // Handle remaining elements in 'arr1' (if any)
    while (i < n)
    {
        if (arr1[i] != temp.back())
        {
            temp.push_back(arr1[i]);
        }
        i++;
    }

    // Handle remaining elements in 'arr2' (if any)
    while (j < m)
    {
        if (arr2[j] != temp.back())
        {
            temp.push_back(arr2[j]);
        }
        j++;
    }

    return temp;
}

Logic:

Initialize Pointers: Use two pointers, one for each array.
Compare Elements: Compare elements at both pointers and add the smaller one to the result if it's not a duplicate.
Advance Pointers: Move the pointer forward for the array from which the element was taken.
Handle Remaining Elements: Add any remaining elements from either array.

Time Complexity: O(m+n)

Explanation: In the worst case, each element in both arrays is processed exactly once, resulting in O(m+n) time complexity.

Space Complexity: O(m+n)

Explanation: The temporary vector temp stores the union of elements from both arrays. In the worst case where there are no duplicates, temp will contain m + n elements. Therefore, the space complexity is O(m+n) considering the temporary vector.

If we do not consider the space for the temporary vector, the space complexity is O(1) as we are only using a constant amount of extra space for variables i and j.

Example:

Input: arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], n = 10, arr2 = [2, 3, 4, 4, 5, 11, 12], m = 7
Output: union = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Explanation: Elements from both arrays are merged without duplicates.

Comparison

Brute Force Method (Using Set):
- Pros: Simple and straightforward.
- Cons: Less efficient for large arrays due to O((m+n) log(m+n)) time complexity.
Optimal Method (Using Two Pointers):
- Pros: Efficient with O(m+n) time complexity.
- Cons: Slightly more complex to implement but highly efficient for large arrays.

Edge Cases

Empty Arrays: Returns an empty array.
No Common Elements: Returns all elements from both arrays.
All Elements Common: Returns the common elements without duplicates.

Additional Notes

Efficiency: The two-pointers method is more time-efficient.
Practicality: The choice between methods depends on the specific constraints and requirements of the problem.

Conclusion

Finding the union of two sorted arrays can be efficiently achieved using either a set or a two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.

How to Move Zeros to the End of an Array

Mahbub Alam Masum — Sat, 15 Jun 2024 19:13:55 +0000

Moving zeros to the end of an array while maintaining the order of non-zero elements is a common problem in programming. In this article, we'll discuss two approaches to achieve this: one using a temporary array and another using a two-pointers technique.

Solution 1: Brute Force Approach (using a Temp Array)

This method involves creating an auxiliary array to store the non-zero elements and then filling the original array with these elements followed by zeros.

Implementation:

// Solution-1: Brute Force Approach (Using a Temp Array)
// Time Complexity: O(n) + O(x) + O(n-x) ~ O(2n)
// n = total number of elements
// x = number of non-zero elements
// n-x = total number of zeros

// Space Complexity: O(n)
// In the worst case, all elements can be non-zero.
void moveAllZerosToEnd(vector<int> &arr, int n)
{
    vector<int> temp;

    // Push non-zero elements to the temp vector.
    for (int i = 0; i < n; i++)
    {
        if (arr[i] != 0)
        {
            temp.push_back(arr[i]);
        }
    }

    // Number of non-zero elements
    int nz = temp.size();

    // Copy all non-zeros to main vector
    for (int i = 0; i < nz; i++)
    {
        arr[i] = temp[i];
    }

    // Fill the remaining elements of the main vector with zeros
    for (int i = nz; i < n; i++)
    {
        arr[i] = 0;
    }
}

Logic:

Push Non-Zeros to Temp: Traverse the array and push all non-zero elements to a temporary array.
Copy Non-Zeros Back: Copy the elements from the temporary array back to the original array.
Fill Zeros: Fill the remaining elements of the original array with zeros.

Time Complexity: O(n)

Explanation: The array is traversed twice.

Space Complexity: O(n)

Explanation: An additional array is used to store non-zero elements. In the worst case, all elements can be non-zero.

Example:

Input: arr = [0, 1, 0, 3, 12], n = 5
Output: arr = [1, 3, 12, 0, 0]
Explanation: Non-zero elements are moved to the front and zeros to the end.

Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to efficiently rearrange the array in-place without using extra space.

Implementation:

// Solution-2: Optimal Approach (Using Two Pointers)
// Time Complexity: O(n)
// Space Complexity: O(1)
void moveAllZerosToEnd(vector<int> &arr, int n)
{
    int j = -1;
    // Find the first zero (if any)
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
        {
            j = i;
            break;
        }
    }

    // If no-zeros, return
    if (j == -1)
    {
        return;
    }

    // If non-zero found, swap it with the element at index 'j'.
    for (int i = j + 1; i < n; i++)
    {
        if (arr[i] != 0)
        {
            swap(arr[j], arr[i]);
            j++;
        }
    }
}

Logic:

Find First Zero: Find the index of the first zero.
Swap Non-Zero Elements: Traverse the array and swap each non-zero element with the element at the found zero index j.
Increment Zero Index: After each swap, increment the zero index j.

Time Complexity: O(n)

Explanation: The array is traversed once.

Space Complexity: O(1)

Explanation: The algorithm operates in place, using only a constant amount of extra space.

Example:

Input: arr = [0, 1, 0, 3, 12], n = 5
Output: arr = [1, 3, 12, 0, 0]
Explanation: Non-zero elements are moved to the front and zeros to the end.

Comparison

Temp Array Method:
- Pros: Simple and easy to understand.
- Cons: Uses additional space, which may not be efficient for large arrays.
Two Pointers Method:
- Pros: Efficient with O(n) time complexity and O(1) space complexity.
- Cons: Slightly more complex to implement but highly efficient for large arrays.

Edge Cases

Empty Array: Returns immediately as there are no elements to move.
All Zeros: The array remains unchanged.
No Zeros: The array remains unchanged.

Additional Notes

Efficiency: The two-pointers method is more space-efficient, making it preferable for large arrays.
Practicality: Both methods handle the problem efficiently but the choice depends on space constraints.

Conclusion

Moving zeros to the end of an array can be efficiently achieved using either a temporary array or an in-place two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.

How to Right Rotate an Array by D Positions

Mahbub Alam Masum — Sat, 15 Jun 2024 09:26:43 +0000

Right rotating an array involves shifting the elements of the array to the right by a specified number of places. In this article, we'll discuss two efficient methods to achieve this rotation.

Solution 1: Brute Force Approach (using a Temp Array)

This method uses an auxiliary array to store the last D elements and then shifts the rest of the elements to the right.

Implementation:

// Solution-1: Using a Temp Array
// Time Complexity: O(n)
// Space Complexity: O(k)
// since k array elements need to be stored in temp array
void rightRotate1(int arr[], int n, int k)
{
    // Adjust k to be within the valid range (0 to n-1)
    k = k % n;

    // Handle edge case: empty array
    if (n == 0)
    {
        return;
    }

    int temp[k];

    // Storing k elements in temp array from the right
    for (int i = n - k; i < n; i++)
    {
        temp[i - n + k] = arr[i];
    }

    // Shifting the rest of elements to the right
    for (int i = n - k - 1; i >= 0; i--)
    {
        arr[i + k] = arr[i];
    }

    // Putting k elements back to main array
    for (int i = 0; i < k; i++)
    {
        arr[i] = temp[i];
    }
}

Logic:

Adjust k: Ensure k is within the valid range by taking k % n.
Store in Temp: Store the last k elements in a temporary array.
Shift Elements: Shift the remaining elements of the array to the right by k positions.
Copy Back: Copy the elements from the temporary array back to the start of the main array.

Time Complexity: O(n)

Explanation: Each element is moved once.

Space Complexity: O(k)

Explanation: An additional array of size k is used.

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: arr = [5, 6, 7, 1, 2, 3, 4]
Explanation: The last 3 elements [5, 6, 7] are stored in a temp array, the rest are shifted right and then the temp array is copied back to the start.

Solution 2: Optimal Approach (using Reversal Algorithm)

This method uses a three-step reversal process to achieve the rotation without needing extra space.

Implementation:

// Solution-2: Using Reversal Algorithm
// Time Complexity: O(n)
// Space Complexity: O(1)

// Function to Reverse Array
void reverseArray(int arr[], int start, int end)
{
    while (start < end)
    {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// Function to Rotate k elements to the right
void rightRotate2(int arr[], int n, int k)
{
    // Adjust k to be within the valid range (0 to n-1)
    k = k % n;

    // Handle edge case: empty array
    if (n == 0)
    {
        return;
    }

    // Reverse first n-k elements
    reverseArray(arr, 0, n - 1 - k);

    // Reverse last k elements
    reverseArray(arr, n - k, n - 1);

    // Reverse whole array
    reverseArray(arr, 0, n - 1);
}

Logic:

Adjust k: Ensure k is within the valid range by taking k % n.
Reverse First Part: Reverse the first n - k elements.
Reverse Second Part: Reverse the remaining k elements.
Reverse Entire Array: Reverse the entire array to achieve the final rotated array.

Time Complexity: O(n)

Explanation: The array is reversed three times, each taking O(n) time.

Space Complexity: O(1)

Explanation: The algorithm operates in place, using only a constant amount of extra space.

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: arr = [5, 6, 7, 1, 2, 3, 4]
Explanation:
- Reverse the first 4 elements: [4, 3, 2, 1, 5, 6, 7]
- Reverse the last 3 elements: [4, 3, 2, 1, 7, 6, 5]
- Reverse the entire array: [5, 6, 7, 1, 2, 3, 4]

Comparison

Temp Array Method:
- Pros: Simple and easy to understand.
- Cons: Uses additional space for the temporary array, which may not be efficient for large values of k.
Reversal Algorithm:
- Pros: Efficient with O(n) time complexity and O(1) space complexity.
- Cons: Slightly more complex to implement but highly efficient for large arrays.

Edge Cases

Empty Array: Returns immediately as there are no elements to rotate.
k >= n: Correctly handles cases where k is greater than or equal to the array length by using k % n.
Single Element Array: Returns the same array as it only contains one element.

Additional Notes

Efficiency: The reversal algorithm is more space-efficient, making it preferable for large arrays.
Practicality: Both methods handle rotations efficiently but the choice depends on space constraints.

Conclusion

Right rotating an array by k positions can be efficiently achieved using either a temporary array or an in-place reversal algorithm. The optimal choice depends on the specific constraints and requirements of the problem.

How to Left Rotate an Array by D Positions

Mahbub Alam Masum — Sat, 15 Jun 2024 09:07:20 +0000

Left rotating an array involves shifting the elements of the array to the left by a specified number of places. In this article, we'll discuss two efficient methods to achieve this rotation.

Solution 1: Brute Force Approach (using a Temp Array)

This method uses an auxiliary array to store the first D elements and then shifts the rest of the elements to the left.

Implementation:

// Solution-1: Using a Temp Array
// Time Complexity: O(n)
// Space Complexity: O(k)
// since k array elements need to be stored in temp array
void leftRotate(int arr[], int n, int k)
{
    // Adjust k to be within the valid range (0 to n-1)
    k = k % n;

    // Handle edge case: empty array
    if (n == 0)
    {
        return;
    }

    int temp[k];

    // Storing k elements in temp array from the left
    for (int i = 0; i < k; i++)
    {
        temp[i] = arr[i];
    }

    // Shifting the rest of elements to the left
    for (int i = k; i < n; i++)
    {
        arr[i - k] = arr[i];
    }

    // Putting k elements back to main array
    for (int i = n - k; i < n; i++)
    {
        arr[i] = temp[i - n + k];
    }
}

Logic:

Adjust k: Ensure k is within the valid range by taking k % n.
Store in Temp: Store the first k elements in a temporary array.
Shift Elements: Shift the remaining elements of the array to the left by k positions.
Copy Back: Copy the elements from the temporary array back to the end of the main array.

Time Complexity: O(n)

Explanation: Each element is moved once.

Space Complexity: O(k)

Explanation: An additional array of size k is used.

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: arr = [4, 5, 6, 7, 1, 2, 3]
Explanation: The first 3 elements [1, 2, 3] are stored in a temp array, the rest are shifted left and then the temp array is copied back to the end.

Solution 2: Optimal Approach (using Reversal Algorithm)

This method uses a three-step reversal process to achieve the rotation without needing extra space.

Implementation:

// Solution-2: Using Reversal Algorithm
// Time Complexity: O(n)
// Space Complexity: O(1)

// Function to Reverse Array
void reverseArray(int arr[], int start, int end)
{
    while (start < end)
    {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// Function to Rotate k elements to the left
void leftRotate(int arr[], int n, int k)
{
    // Adjust k to be within the valid range (0 to n-1)
    k = k % n;

    // Handle edge case: empty array
    if (n == 0)
    {
        return;
    }

    // Reverse first k elements
    reverseArray(arr, 0, k - 1);

    // Reverse last n-k elements
    reverseArray(arr, k, n - 1);

    // Reverse whole array
    reverseArray(arr, 0, n - 1);
}

Logic:

Adjust k: Ensure k is within the valid range by taking k % n.
Reverse First Part: Reverse the first k elements.
Reverse Second Part: Reverse the remaining n-k elements.
Reverse Entire Array: Reverse the entire array to achieve the final rotated array.

Time Complexity: O(n)

Explanation: The array is reversed three times, each taking O(n) time.

Space Complexity: O(1)

Explanation: The algorithm operates in place, using only a constant amount of extra space.

Example:

Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: arr = [4, 5, 6, 7, 1, 2, 3]
Explanation:
- Reverse the first 3 elements: [3, 2, 1, 4, 5, 6, 7]
- Reverse the last 4 elements: [3, 2, 1, 7, 6, 5, 4]
- Reverse the entire array: [4, 5, 6, 7, 1, 2, 3]

Comparison

Brute Force Method (Using Temp Array):
- Pros: Simple and easy to understand.
- Cons: Uses additional space for the temporary array, which may not be efficient for large values of k.
Optimal Method (Using Reversal Algorithm):
- Pros: Efficient with O(n) time complexity and O(1) space complexity.
- Cons: Slightly more complex to implement but highly efficient for large arrays.

Edge Cases

Empty Array: Returns immediately as there are no elements to rotate.
k >= n: Correctly handles cases where k is greater than or equal to the array length by using k % n.
Single Element Array: Returns the same array as it only contains one element.

Additional Notes

Efficiency: The reversal algorithm is more space-efficient, making it preferable for large arrays.
Practicality: Both methods handle rotations efficiently but the choice depends on space constraints.

Conclusion

Left rotating an array by k positions can be efficiently achieved using either a temporary array or an in-place reversal algorithm. The optimal choice depends on the specific constraints and requirements of the problem.

How to Remove Duplicates from a Sorted Array

Mahbub Alam Masum — Fri, 07 Jun 2024 09:43:29 +0000

Removing duplicates from a sorted array is a common problem asked in many coding interviews and programming challenges. This can be approached using different methods. In this article, we'll discuss two approaches to remove duplicates from a sorted array: one using set and another using the two-pointers technique.

Solution 1: Brute Force Approach (using Set)

This method uses a set to store unique elements, ensuring that duplicates are removed.

Implementation:

// Solution-1: Brute Force Approach (using Set)
// Time Complexity: O(nlogn)
// Space Complexity: O(n)
int removeDuplicates(vector<int> &arr, int n)
{
    set<int> uniqueElements;

    for (int i = 0; i < n; i++)
    {
        uniqueElements.insert(arr[i]);
    }

    int k = uniqueElements.size();

    // Copy unique elements from the set back into the input array
    int i = 0;
    for (auto x : uniqueElements)
    {
        arr[i] = x;
        i++;
    }

    // Return the number of unique elements
    return k;

}

Logic:

Use a Set: Insert all elements of the array into a set to remove duplicates.
Get Unique Count: The size of the set gives the number of unique elements.
Copy Back to Array: Copy elements from the set back to the array.

Time Complexity: O(n log n)

Explanation: Inserting each element into the set takes O(log n) time, resulting in O(n log n) for n elements.

Space Complexity: O(n)

Explanation: The set stores all unique elements, potentially up to n elements.

Example:

Input: arr = [1, 1, 2, 2, 3, 4, 4], n = 7
Output: k = 4, arr = [1, 2, 3, 4, ...]
Explanation: The array contains 4 unique elements.

Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to overwrite duplicates in place, providing an efficient solution.

Implementation:

// Solution-2: Optimal Approach (Two-Pointers Technique)
// Time Complexity: O(n)
// Space Complexity: O(1)
int removeDuplicates(vector<int> &arr, int n)
{
    int i = 0; // Pointer to track the position of the next unique element
    for (int j = 1; j < n; j++)
    {
        if (arr[i] != arr[j])
        {
            i++;
            arr[i] = arr[j];
        }
    }

    // Return the number of unique elements
    return i + 1;
}

Logic:

Initialize Pointers: Use i to track the position of the next unique element and j to traverse the array.
Compare Elements: If arr[i] is not equal to arr[j], increment i and update arr[i] with arr[j].
Return Count: The value i + 1 gives the number of unique elements.

Time Complexity: O(n)

Explanation: The array is traversed once.

Space Complexity: O(1)

Explanation: No additional space is used apart from variables.

Example:

Input: arr = [1, 1, 2, 2, 3, 4, 4], n = 7
Output: k = 4, arr = [1, 2, 3, 4, ...]
Explanation: The array contains 4 unique elements.

Comparison

Brute Force Method:
- Pros: Simple and straightforward.
- Cons: Inefficient for large arrays due to O(n log n) time complexity and additional space usage.
- Use Case: Useful when simplicity is more important than efficiency.
Optimal Method:
- Pros: Efficient with O(n) time complexity and O(1) space complexity.
- Cons: Requires in-place modification of the array.
- Use Case: Ideal for large arrays and when in-place operations are feasible.

Edge Cases

Empty Array: Returns 0 as there are no elements.
Single Element Array: Returns 1 as a single element is trivially unique.
All Identical Elements: Returns 1 as all elements are the same.

Additional Notes

Efficiency: The optimal approach is significantly more efficient for large datasets.
Simplicity: Despite its efficiency, the optimal approach is simple to implement.
Practicality: The optimal method is generally preferred due to its linear time complexity and constant space complexity.

Conclusion

Removing duplicates from a sorted array can be done efficiently using an in-place approach with two pointers. While the brute force method provides a straightforward solution, the optimal approach is both efficient and easy to implement, making it suitable for large datasets.

How to Check if an Array is Sorted

Mahbub Alam Masum — Tue, 04 Jun 2024 18:01:00 +0000

There are many times we need to check if an array is sorted or not. Checking if an array is sorted can be approached in multiple ways. Here, we we'll discuss two solutions: a brute force approach and an optimal approach.

Solution 1: Brute Force Approach

This method involves comparing each element with every other element that comes after it in the array to ensure that the array is sorted in non-decreasing order.

Implementation:

// Solution-1: Brute Force Approach
// Time Complexity: O(n*n)
// Space Complexity: O(1)
bool isArraySorted(vector<int> &arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[i])
                return false;
        }
    }
    return true;
}

Logic:

1. Nested Loops: Use two nested loops to compare each element with every subsequent element in the array.

2. Check Order: If any element is found to be greater than a subsequent element, the array is not sorted and the function returns false.

3. Return True: If no such pair is found, the array is sorted and the function returns true.

Time Complexity: O(n²)

Explanation: The outer loop runs n times and for each iteration, the inner loop runs up to n-1 times, resulting in a quadratic time complexity.

Space Complexity: O(1)

Explanation: The algorithm uses a constant amount of extra space.

Example:

Input: arr = [10, 20, 30, 40, 50], n = 5
Output: true
Explanation: All elements are in non-decreasing order.

Solution 2: Optimal Approach

A more efficient method involves a single pass through the array, comparing each element with its predecessor to ensure that the array is sorted.

Implementation:

// Solution-2: Optimal Approach
// Time Complexity: O(n)
// Space Complexity: O(1)
bool isArraySorted(vector<int> &arr, int n)
{
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[i - 1])
        {
            return false;
        }
    }
    return true;
}

Logic:

1. Single Loop: Traverse the array starting from the second element.

2. Compare with Predecessor: For each element, check if it is less than its predecessor.

3. Return False: If any element is found to be less than its predecessor, the array is not sorted and the function returns false.

4. Return True: If no such element is found, the array is sorted and the function returns true.

Time Complexity: O(n)

Explanation: The algorithm makes a single pass through the array, resulting in linear time complexity.

Space Complexity: O(1)

Explanation: The algorithm uses a constant amount of extra space.

Example:

Input: arr = [10, 20, 30, 40, 50], n = 5
Output: true
Explanation: All elements are in non-decreasing order.

Comparison

Brute Force Method:
- Pros: Simple and easy to understand.
- Cons: Inefficient due to its O(n²) time complexity.
- Use Case: Not suitable for large arrays due to its inefficiency.
Optimal Method:
- Pros: Highly efficient with O(n) time complexity.
- Cons: None significant.
- Use Case: Ideal for checking the sorted status of large arrays.

Edge Cases

Empty Array: An empty array is considered sorted.
Single Element Array: An array with a single element is considered sorted.
Array with All Identical Elements: An array where all elements are the same is considered sorted.

Additional Notes

Efficiency: The optimal approach is significantly more efficient for large datasets.
Simplicity: Despite its efficiency, the optimal approach is also simple to implement.
Practicality: The optimal method is generally preferred due to its linear time complexity and constant space complexity.

Conclusion

Checking if an array is sorted can be done efficiently using a single-pass approach. While the brute force method provides a simple but inefficient solution, the optimal method is both efficient and easy to implement, making it suitable for large datasets.

How to Find the Second Largest Element in an Array

Mahbub Alam Masum — Mon, 03 Jun 2024 19:28:41 +0000

Finding the second largest element in an array can be approached in multiple ways. Here, we'll discuss three methods: using sorting, a better approach with two linear traversals and an optimal single-pass approach.

Solution 1: Sorting

One straightforward method to find the second largest element in an array is by sorting the array in ascending order and then traversing the sorted array from the end to find the second largest unique element.

Implementation:

// Solution-1: Sorting
// Time Complexity: O(n log n)
// Space Complexity: O(1)
int secondLargestElement(vector<int> &arr)
{
    sort(arr.begin(), arr.end());

    int large = arr[arr.size() - 1];
    int secondLarge = large;

    for (int i = arr.size() - 2; i >= 0; i--)
    {
        if (arr[i] != large)
        {
            secondLarge = arr[i];
            break;
        }
    }
    return secondLarge;
}

Logic:

1. Sort the array: Use the sort function to sort the array in ascending order.

2. Find the second largest element: Traverse the sorted array from the end to find the first element that is not equal to the largest element.

Time Complexity: O(n log n)

Explanation: The time complexity is dominated by the sorting algorithm.

Space Complexity: O(1)

Explanation: Sorting is done in place, so no additional space is used.

Example:

Input: arr = [10, 20, 5, 3, 100]
Output: 20
Explanation: The sorted array is [3, 5, 10, 20, 100]. The second largest element is 20.

Solution 2: Better Approach

A more efficient method is to use two linear traversals of the array. First, find the largest element and then find the second largest element excluding the largest one.

Implementation:

// Solution-2: Better Approach
// Time Complexity: O(n), We do two linear traversals in our array
// Space Complexity: O(1)
int secondLargestElement(vector<int> &arr, int n)
{
    // Find the largest element in the array
    int large = arr[0];
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > large)
        {
            large = arr[i];
        }
    }

    // Find the second largest element excluding the largest one
    int secondLarge = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > secondLarge && arr[i] != large)
        {
            secondLarge = arr[i];
        }
    }
    return secondLarge;
}

Logic:

1. Find the largest element: Traverse the array to find the largest element.

2. Find the second largest element: Traverse the array again to find the largest element excluding the previously found largest element.

Time Complexity: O(n)

Explanation: Two separate linear traversals of the array.

Space Complexity: O(1)

Explanation: Only a constant amount of extra space is used.

Example:

Input: arr = [10, 20, 5, 3, 100]
Output: 20
Explanation: The largest element is 100. The second largest element found during the second traversal is 20.

Solution 3: Optimal Approach

The most efficient method is a single-pass solution where we keep track of both the largest and second largest elements during one traversal of the array.

Implementation:

// Solution-3: Optimal Approach
// Time Complexity: O(n), Single-pass solution
// Space Complexity: O(1)
int secondLargestElement(vector<int> &arr, int n)
{
    int large = INT_MIN;
    int secondLarge = INT_MIN;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] > large)
        {
            secondLarge = large;
            large = arr[i];
        }
        else if (arr[i] > secondLarge && arr[i] != large)
        {
            secondLarge = arr[i];
        }
    }
    return secondLarge;
}

Logic:

1. Initialize large and secondLarge: Set them to the smallest possible integer values INT_MIN.

2. Single-pass traversal: During one traversal of the array, update large and secondLarge accordingly.

3. Update logic: If the current element is greater than large, update secondLarge to be large and then update large. Otherwise, if the current element is greater than secondLarge and not equal to large, update secondLarge.

Time Complexity: O(n)

Explanation: Single linear traversal of the array.

Space Complexity: O(1)

Explanation: Only a constant amount of extra space is used.

Example:

Input: arr = [10, 20, 5, 3, 100]
Output: 20
Explanation: The traversal updates large to 100 and secondLarge to 20.

Comparison

Sorting Method:
- Pros: Simple and easy to implement.
- Cons: Less efficient due to the O(n log n) time complexity.
- Use Case: Suitable when sorting the array is required for other purposes.
Better Approach:
- Pros: More efficient with O(n) time complexity using two passes.
- Cons: Requires two traversals of the array.
- Use Case: Useful when you want a more efficient solution than sorting but don’t mind two passes.
Optimal Approach:
- Pros: Most efficient with O(n) time complexity using a single pass.
- Cons: Slightly more complex logic.
- Use Case: Ideal for finding the second largest element in large datasets efficiently.

Edge Cases

Empty Array: If the array is empty, the function should handle it by returning an appropriate value or throwing an exception.
Single Element Array: If the array contains only one element, there is no second largest element, so the function should handle this case appropriately.
All Elements Same: If all elements in the array are the same, there is no distinct second largest element, so the function should handle this case appropriately.

Additional Notes

Stability: Since we are only finding the second largest element, stability (preserving the order of equal elements) is not relevant.
Efficiency: The optimal approach is the most efficient for large datasets due to its single-pass solution.
Use Cases: The optimal method is generally preferred for its O(n) time complexity and O(1) space complexity, making it suitable for large datasets.

Conclusion

Finding the second largest element in an array can be done efficiently using various methods. The sorting approach is simple but less efficient, while the better and optimal approaches provide more efficient solutions with linear time complexity. Understanding these approaches provides valuable insights into different problem-solving strategies and their trade-offs.

How to Find the Largest Element in an Array

Mahbub Alam Masum — Mon, 03 Jun 2024 19:15:41 +0000

Finding the largest element in an array is a common problem that can be approached in different ways. Here, we'll discuss two methods: one using sorting and the other using an iterative approach.

Solution 1: Sorting

One straightforward method to find the largest element in an array is by sorting the array in ascending order and then selecting the last element.

Implementation:

// Solution-1: Sorting 
// (Sort the array in ascending order & get the last element)
// Time Complexity: O(nlogn)
// Space Complexity: O(1)
int findLargestElement(vector<int> &arr)
{
    sort(arr.begin(), arr.end());

    // Return the last element of the sorted array
    return arr[arr.size() - 1];
}

Logic:

1. Sort the array: Use the sort function to sort the array in ascending order.

2. Return the last element: The largest element will be the last element in the sorted array.

Time Complexity: O(n log n)

Explanation: The time complexity is dominated by the sorting algorithm.

Space Complexity: O(1)

Explanation: Sorting is done in place, so no additional space is used.

Example:

Input: arr = [10, 20, 5, 3, 100]
Output: 100
Explanation: The sorted array is [3, 5, 10, 20, 100] and the last element is 100.

Solution 2: Iterative Approach

A more efficient method is to iterate through the array while keeping track of the maximum element found so far.

Implementation:

// Solution-2: Iterative Approach
// (Using a max variable)
// Time Complexity: O(n)
// Space Complexity: O(1)
int findLargestElement(vector<int> &arr, int n)
{
    int max = arr[0];

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

Logic:

1. Initialize max variable: Set max to the first element of the array.

2. Iterate through the array: Compare each element with max.

3. Update max: If the current element is greater than max, update max with the current element.

4. Return max: After completing the iteration, max holds the largest element.

Time Complexity: O(n)

Explanation: The array is traversed once.

Space Complexity: O(1)

Explanation: Only a constant amount of extra space is used.

Example:

Input: arr = [10, 20, 5, 3, 100]
Output: 100
Explanation: The largest element found during the iteration is 100.

Comparison

Sorting Method:
- Pros: Simple and easy to implement.
- Cons: Less efficient due to the O(n log n) time complexity.
- Use Case: Suitable when sorting the array is required for other purposes.
Iterative Method:
- Pros: More efficient with O(n) time complexity.
- Cons: Slightly more complex logic.
- Use Case: Ideal for finding the largest element when sorting is not needed.

Edge Cases

Empty Array: If the array is empty, the function should handle it by returning an appropriate value or throwing an exception.
Single Element Array: If the array contains only one element, that element is the largest by default.
All Elements Same: If all elements in the array are the same, the function should correctly return that element as the largest.

Additional Notes

Stability: Since we are only finding the largest element, stability (preserving the order of equal elements) is not relevant.
Efficiency: The iterative approach is more efficient for large datasets compared to the sorting method.
Use Cases: The iterative method is generally preferred for its O(n) time complexity and O(1) space complexity, making it suitable for large datasets.

Conclusion

Both methods are effective for finding the largest element in an array but the iterative approach is more efficient in terms of time complexity. Understanding both approaches provides valuable insights into different problem-solving strategies and their trade-offs.