# Find Second Smallest and Second Largest Element in an array

Problem Statement: Given an array, find the second smallest and second largest element in the array. Print ‘-1’ in the event that either of them doesn’t exist.

Examples
```Example 1:
Input: [1,2,4,7,7,5]
Output: Second Smallest : 2
Second Largest : 5
Explanation: The elements are as follows 1,2,3,5,7,7 and hence second largest of these is 5 and second smallest is 2

Example 2:
Input: [1]
Output: Second Smallest : -1
Second Largest : -1
Explanation: Since there is only one element in the array, it is the largest and smallest element present in the array. There is no second largest or second smallest element present.

```
Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute-Force Approach Better Approach Optimal Approach
Brute Force Approach
Algorithm / Intuition

### Intuition:

What do we do to find the largest or the smallest element present in an array? We ideally sort them and the first element would be the smallest of all while the last element would be the largest. Can we find the second-smallest and second-largest using a similar approach?

### Approach:

• Sort the array in ascending order
• The element present at the second index is the second smallest element
• The element present at the second index from the end is the second largest element
Code
``````
#include<bits/stdc++.h>
using namespace std;
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
sort(arr,arr+n);
int small=arr[1];
int large=arr[n-2];
cout<<"Second smallest is "<<small<<endl;
cout<<"Second largest is "<<large<<endl;
}
int main()
{
int arr[]={1,2,4,6,7,5};
int n=sizeof(arr)/sizeof(arr[0]);
getElements(arr,n);
return 0;
}

```
```

Output:

Second smallest is 2
Second largest is 6

``````
import java.io.*;
import java.util.Arrays;
class Test
{
static private void getElements(int[] arr, int n)
{
if (n == 0 || n==1)
{
System.out.print(-1);
System.out.print(" ");
System.out.print(-1);
System.out.print("\n");
}
Arrays.sort(arr);
int small = arr[1];
int large = arr[n - 2];
System.out.println("Second smallest is "+small);
System.out.println("Second largest is "+large);
}
public static void main(String[] args)
{
int[] arr = {1, 2, 4, 6, 7, 5};
int n = arr.length;
getElements(arr, n);
}
}
```
```

Output:

Second smallest is 2
Second largest is 6

``````
def getElements(arr, n):
if n == 0 or n == 1:
print(-1, -1)  # edge case when only one element is present in array
arr.sort()
small = arr[1]
large = arr[n-2]
print("Second smallest is", small)
print("Second largest is", large)

if __name__ == '__main__':
arr = [1, 2, 4, 6, 7, 5]
n = len(arr)
getElements(arr, n)
```
```

Output:

Second smallest is 2
Second largest is 6

``````
function getElements(arr) {
if (arr.length === 0 || arr.length === 1) {
console.log(-1 + " " + -1); // Edge case when only one element is present in the array
return;
}

arr.sort((a, b) => a - b);
let small = arr[1];
let large = arr[arr.length - 2];
console.log("Second smallest is " + small);
console.log("Second largest is " + large);
}

const arr = [1, 2, 4, 6, 7, 5];
getElements(arr);

```
```

Output:

Second smallest is 2
Second largest is 6

Complexity Analysis

Time Complexity: O(NlogN), For sorting the array

Space Complexity: O(1)

Better Approach
Algorithm / Intuition

## Solution 2(Better Solution)

### Intuition:

Even though we want to have just the second smallest and largest elements, we are still sorting the entire array for that and thus increasing the time complexity. Can we somehow try to not sort the array and still get our answer?

### Approach:

• Find the smallest and largest element in the array in a single traversal
• After this, we once again traverse the array and find an element that is just greater than the smallest element we just found.
• Similarly, we would find the largest element which is just smaller than the largest element we just found
• Indeed, this is our second smallest and second largest element.
Code
``````
#include<bits/stdc++.h>
using namespace std;
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;
}
int main()
{
int arr[]={1,2,4,6,7,5};
int n=sizeof(arr)/sizeof(arr[0]);
getElements(arr,n);
return 0;
}
```
```

Output:

Second smallest is 2
Second largest is 6

``````
import java.io.*;
import java.util.Arrays;
class Test
{
static private void getElements(int[] arr, int n)
{
if (n == 0 || n==1)
{
System.out.print(-1);
System.out.print(" ");
System.out.print(-1);
System.out.print("\n");
}
int small = Integer.MAX_VALUE;
int second_small = Integer.MAX_VALUE;
int large = Integer.MIN_VALUE;
int second_large = Integer.MIN_VALUE;
int i;
for (i = 0;i < n;i++)
{
small = Math.min(small,arr[i]);
large = Math.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];
}
}

System.out.println("Second smallest is "+second_small);
System.out.println("Second largest is "+second_large);
}
public static void main(String[] args)
{
int[] arr = {1, 2, 4, 6, 7, 5};
int n = arr.length;
getElements(arr, n);
}
}

```
```

Output:

Second smallest is 2
Second largest is 6

``````
def getElements(arr, n):
if n == 0 or n == 1:
print(-1, -1)  # edge case when only one element is present in array
small = float('inf')
second_small = float('inf')
large = float('-inf')
second_large = float('-inf')
for i in range(n):
small = min(small, arr[i])
large = max(large, arr[i])
for i in range(n):
if arr[i] < second_small and arr[i] != small:
second_small = arr[i]
if arr[i] > second_large and arr[i] != large:
second_large = arr[i]
print("Second smallest is", second_small)
print("Second largest is", second_large)

if __name__ == '__main__':
arr = [1, 2, 4, 6, 7, 5]
n = len(arr)
getElements(arr, n)

```
```

Output:

Second smallest is 2
Second largest is 6

``````

function getElements(arr) {
if (arr.length === 0 || arr.length === 1) {
console.log(-1 + " " + -1); // Edge case when only one element is present in the array
return;
}

let small = Infinity;
let second_small = Infinity;
let large = -Infinity;
let second_large = -Infinity;

for (let i = 0; i < arr.length; i++) {
small = Math.min(small, arr[i]);
large = Math.max(large, arr[i]);
}

for (let i = 0; i < arr.length; 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];
}

console.log("Second smallest is " + second_small);
console.log("Second largest is " + second_large);
}

const arr = [1, 2, 4, 6, 7, 5];
getElements(arr);
```
```

Output:

Second smallest is 2
Second largest is 6

Complexity Analysis

Time Complexity: O(N), We do two linear traversals in our array

Space Complexity: O(1)

Optimal Approach
Algorithm / Intuition

### Intuition:

In the previous solution, even though we were able to bring down the time complexity to O(N), we still needed to do two traversals to find our answer. Can we do this in a single traversal by using smart comparisons on the go?

#### Approach:

We would require four variables: small,second_small, large, and second_large. Variable small and second_small are initialized to INT_MAX while large and second_large are initialized to INT_MIN.

Second Smallest Algo:

• If the current element is smaller than ‘small’, then we update second_small and small variables
• Else if the current element is smaller than ‘second_small’ then we update the variable ‘second_small’
• Once we traverse the entire array, we would find the second smallest element in the variable second_small.
• Here’s a quick demonstration of the same.

Second Largest Algo:

• If the current element is larger than ‘large’ then update second_large and large variables
• Else if the current element is larger than ‘second_large’ then we update the variable second_large.
• Once we traverse the entire array, we would find the second largest element in the variable second_large.
• Here’s a quick demonstration of the same.
Code
``````

#include<bits/stdc++.h>
using namespace std;
int secondSmallest(int arr[],int n)
{
if(n<2)
return -1;
int small = INT_MAX;
int second_small = INT_MAX;
int i;
for(i = 0; i < n; i++)
{
if(arr[i] < small)
{
second_small = small;
small = arr[i];
}
else if(arr[i] < second_small && arr[i] != small)
{
second_small = arr[i];
}
}
return second_small;
}
int secondLargest(int arr[],int n)
{
if(n<2)
return -1;
int large=INT_MIN,second_large=INT_MIN;
int i;
for (i = 0; i < n; i++)
{
if (arr[i] > large)
{
second_large = large;
large = arr[i];
}

else if (arr[i] > second_large && arr[i] != large)
{
second_large = arr[i];
}
}
return second_large;
}

int main() {
int arr[]={1,2,4,7,7,5};
int n=sizeof(arr)/sizeof(arr[0]);
int sS=secondSmallest(arr,n);
int sL=secondLargest(arr,n);
cout<<"Second smallest is "<<sS<<endl;
cout<<"Second largest is "<<sL<<endl;
return 0;
}

```
```

Output:

Second smallest is 2
Second largest is 5

``````

import java.io.*;
class Test
{
static private int secondSmallest(int[] arr, int n)
{
if (n < 2)
{
return -1;
}
int small = Integer.MAX_VALUE;
int second_small = Integer.MAX_VALUE;
int i;
for (i = 0; i < n; i++)
{
if (arr[i] < small)
{
second_small = small;
small = arr[i];
}
else if (arr[i] < second_small && arr[i] != small)
{
second_small = arr[i];
}
}
return second_small;
}
static private int secondLargest(int[] arr, int n)
{
if(n<2)
return -1;
int large = Integer.MIN_VALUE;
int second_large = Integer.MIN_VALUE;
int i;
for (i = 0; i < n; i++)
{
if (arr[i] > large)
{
second_large = large;
large = arr[i];
}

else if (arr[i] > second_large && arr[i] != large)
{
second_large = arr[i];
}
}
return second_large;
}

public static void main(String[] args)
{
int[] arr = {1, 2, 4, 7, 7, 5};
int n = arr.length;
int sS = secondSmallest(arr, n);
int sL = secondLargest(arr, n);
System.out.println("Second smallest is "+sS);
System.out.println("Second largest is "+sL);
}

}

```
```

Output:

Second smallest is 2
Second largest is 5

``````

def secondSmallest(arr, n):
if (n < 2):
return -1
small = float('inf')
second_small = float('inf')
for i in range(n):
if (arr[i] < small):
second_small = small
small = arr[i]
elif (arr[i] < second_small and arr[i] != small):
second_small = arr[i]
return second_small

def secondLargest(arr, n):
if (n < 2):
return -1
large = float('-inf')
second_large = float('-inf')
for i in range(n):
if (arr[i] > large):
second_large = large
large = arr[i]
elif (arr[i] > second_large and arr[i] != large):
second_large = arr[i]
return second_large

if __name__ == "__main__":
arr = [1, 2, 4, 7, 7, 5]
n = len(arr)
sS = secondSmallest(arr, n)
sL = secondLargest(arr, n)
print("Second smallest is", sS)
print("Second largest is", sL)
```
```

Output:

Second smallest is 2
Second largest is 5

``````

function secondSmallest(arr) {
if (arr.length < 2)
return -1;

let small = Infinity;
let second_small = Infinity;

for (let i = 0; i < arr.length; i++) {
if (arr[i] < small) {
second_small = small;
small = arr[i];
} else if (arr[i] < second_small && arr[i] !== small) {
second_small = arr[i];
}
}

return second_small;
}

function secondLargest(arr) {
if (arr.length < 2)
return -1;

let large = -Infinity;
let second_large = -Infinity;

for (let i = 0; i < arr.length; i++) {
if (arr[i] > large) {
second_large = large;
large = arr[i];
} else if (arr[i] > second_large && arr[i] !== large) {
second_large = arr[i];
}
}

return second_large;
}

const arr = [1, 2, 4, 7, 7, 5];
const sS = secondSmallest(arr);
const sL = secondLargest(arr);

console.log("Second smallest is " + sS);
console.log("Second largest is " + sL);

```
```

Output:

Second smallest is 2
Second largest is 5

Complexity Analysis

Time Complexity: O(N), Single-pass solution

Space Complexity: O(1)

Video Explanation