Given an array of n integers. Find the minimum distance between any two occurrences of the minimum integer in the array.
Input : arr[] = {5, 1, 2, 3, 4, 1, 2, 1}
Output : 2
Explanation: The minimum element 1 occurs at
indexes: 1, 5 and 7. So the minimum
distance is 7-5 = 2.
Input : arr[] = {1, 2, 1}
Output : 2
Brute Force Approach: The simplest approach is to find all pair of indexes of minimum element and calculate minimum distance.
Time Complexity: O(n^2), where n is the total number of elements in the array.
- Initialize an array of integers arr[] and find its size n.
- Initialize a variable min_dist with the maximum possible value of an integer (INT_MAX).
- For each element i in the array, check if it is the minimum element in the array using the min_element function.
- If the element is the minimum element, traverse the array again from i+1 to n-1 to find the next occurrence of the minimum element.
- If the next occurrence is found, calculate the distance between the two occurrences (j-i) and update the minimum distance if necessary.
- After all the elements have been checked, print the minimum distance between the two closest minimum values.
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 5, 1, 2, 3, 4, 1, 2, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
int min_dist = INT_MAX;
for ( int i = 0; i < n; i++) {
if (arr[i] == *min_element(arr, arr + n)) {
for ( int j = i + 1; j < n; j++) {
if (arr[j] == *min_element(arr, arr + n)) {
min_dist = min(min_dist, j - i);
}
}
}
}
cout << min_dist << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
int [] arr = { 5 , 1 , 2 , 3 , 4 , 1 , 2 , 1 };
int n = arr.length;
int min_dist = Integer.MAX_VALUE;
int min_value = Arrays.stream(arr).min().orElse(Integer.MAX_VALUE);
for ( int i = 0 ; i < n; i++) {
if (arr[i] == min_value) {
for ( int j = i + 1 ; j < n; j++) {
if (arr[j] == min_value) {
min_dist = Math.min(min_dist, j - i);
}
}
}
}
System.out.println(min_dist);
}
}
|
Python3
import sys
arr = [ 5 , 1 , 2 , 3 , 4 , 1 , 2 , 1 ]
n = len (arr)
min_dist = sys.maxsize
for i in range (n):
if arr[i] = = min (arr):
for j in range (i + 1 , n):
if arr[j] = = min (arr):
min_dist = min (min_dist, j - i)
print (min_dist)
|
C#
using System;
using System.Linq;
class Program {
static void Main() {
int [] arr = { 5, 1, 2, 3, 4, 1, 2, 1 };
int n = arr.Length;
int min_dist = int .MaxValue;
for ( int i = 0; i < n; i++) {
if (arr[i] == arr.Min()) {
for ( int j = i + 1; j < n; j++) {
if (arr[j] == arr.Min()) {
min_dist = Math.Min(min_dist, j - i);
}
}
}
}
Console.WriteLine(min_dist);
}
}
|
Javascript
let arr = [5, 1, 2, 3, 4, 1, 2, 1];
let n = arr.length;
let min_dist = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
if (arr[i] == Math.min(...arr)) {
for (let j = i + 1; j < n; j++) {
if (arr[j] == Math.min(...arr)) {
min_dist = Math.min(min_dist, j - i);
}
}
}
}
console.log(min_dist);
|
Time Complexity: O(n^2)
Auxiliary Space: O(1)
Efficient Approach: An efficient approach will be to observe that distance between index j and i will always be smaller than distance between indexes k and i where, k is greater than j. That is we only have to check distance between consecutive pairs of minimum elements and not all pairs. Below is the step by step algorithm:
- Find the minimum element in the array
- Find all occurrences of minimum element in the array and insert the indexes in a new array or list or vector.
- Check if size of the list of indexes is greater than one or not, i.e. the minimum element occurs atleast twice. If not than return -1.
- Traverse the list of indexes and calculate the minimum difference between any two consecutive indexes.
Below is the implementation of above idea:
C++
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;
int findClosestMin( int arr[], int n)
{
int min = INT_MAX;
for ( int i = 0; i < n; i++)
if (arr[i] < min)
min = arr[i];
vector< int > indexes;
for ( int i = 0; i < n; i++)
if (arr[i] == min)
indexes.push_back(i);
if (indexes.size() < 2)
return -1;
int min_dist = INT_MAX;
for ( int i = 1; i < indexes.size(); i++)
if ((indexes[i] - indexes[i - 1]) < min_dist)
min_dist = (indexes[i] - indexes[i - 1]);
return min_dist;
}
int main()
{
int arr[] = { 5, 1, 2, 3, 4, 1, 2, 1 };
int size = sizeof (arr) / sizeof (arr[0]);
cout << findClosestMin(arr, size);
return 0;
}
|
Java
import java.util.Vector;
class GFG {
static int findClosestMin( int arr[], int n) {
int min = Integer.MAX_VALUE;
for ( int i = 0 ; i < n; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
Vector<Integer> indexes = new Vector<>();
for ( int i = 0 ; i < n; i++) {
if (arr[i] == min) {
indexes.add(i);
}
}
if (indexes.size() < 2 ) {
return - 1 ;
}
int min_dist = Integer.MAX_VALUE;
for ( int i = 1 ; i < indexes.size(); i++) {
if ((indexes.get(i) - indexes.get(i - 1 )) < min_dist) {
min_dist = (indexes.get(i) - indexes.get(i - 1 ));
}
}
return min_dist;
}
public static void main(String args[]) {
int arr[] = { 5 , 1 , 2 , 3 , 4 , 1 , 2 , 1 };
int size = arr.length;
System.out.println(findClosestMin(arr, size));
}
}
|
Python3
import sys
def findClosestMin(arr, n):
min = sys.maxsize
for i in range ( 0 , n):
if (arr[i] < min ):
min = arr[i]
indexes = []
for i in range ( 0 , n):
if (arr[i] = = min ):
indexes.append(i)
if ( len (indexes) < 2 ):
return - 1
min_dist = sys.maxsize
for i in range ( 1 , len (indexes)):
if ((indexes[i] - indexes[i - 1 ]) < min_dist):
min_dist = (indexes[i] - indexes[i - 1 ]);
return min_dist;
arr = [ 5 , 1 , 2 , 3 , 4 , 1 , 2 , 1 ]
ans = findClosestMin(arr, 8 )
print (ans)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static int findClosestMin( int []arr, int n) {
int min = int .MaxValue;
for ( int i = 0; i < n; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
List< int > indexes = new List< int >();
for ( int i = 0; i < n; i++) {
if (arr[i] == min) {
indexes.Add(i);
}
}
if (indexes.Count < 2) {
return -1;
}
int min_dist = int .MaxValue;
for ( int i = 1; i < indexes.Count; i++) {
if ((indexes[i] - indexes[i-1]) < min_dist) {
min_dist = (indexes[i] - indexes[i-1]);
}
}
return min_dist;
}
public static void Main() {
int []arr = {5, 1, 2, 3, 4, 1, 2, 1};
int size = arr.Length;
Console.WriteLine(findClosestMin(arr, size));
}
}
|
PHP
<?php
function findClosestMin( $arr , $n )
{
$min = PHP_INT_MAX;
# find the min element in the array
for ( $i = 0; $i < $n ; $i ++)
if ( $arr [ $i ] < $min )
$min = $arr [ $i ];
$indexes = array () ;
for ( $i = 0; $i < $n ; $i ++)
if ( $arr [ $i ] == $min )
array_push ( $indexes , $i );
if (sizeof( $indexes ) < 2)
return -1;
$min_dist = PHP_INT_MAX;
for ( $i = 1; $i < sizeof( $indexes ); $i ++)
if (( $indexes [ $i ] -
$indexes [ $i - 1]) < $min_dist )
$min_dist = ( $indexes [ $i ] -
$indexes [ $i - 1]);
return $min_dist ;
}
$arr = array ( 5, 1, 2, 3, 4, 1, 2, 1 );
$size = sizeof( $arr );
echo findClosestMin( $arr , $size );
?>
|
Javascript
<script>
function findClosestMin(arr, n) {
let min = Number.MAX_VALUE;
for (let i = 0; i < n; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
let indexes = [];
for (let i = 0; i < n; i++) {
if (arr[i] == min) {
indexes.push(i);
}
}
if (indexes.length < 2) {
return -1;
}
let min_dist = Number.MAX_VALUE;
for (let i = 1; i < indexes.length; i++) {
if ((indexes[i] - indexes[i-1]) < min_dist) {
min_dist = (indexes[i] - indexes[i-1]);
}
}
return min_dist;
}
let arr = [5, 1, 2, 3, 4, 1, 2, 1];
let size = arr.length;
document.write(findClosestMin(arr, size));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us