Given an array of n integers. Find the minimum distance between any two occurrences of the minimum integer in the array.
Examples:
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 sysarr = [5, 1, 2, 3, 4, 1, 2, 1]n = len(arr)min_dist = sys.maxsizefor 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); |
Output
2
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++
// CPP program to find Distance between// two closest minimum#include <iostream>#include <limits.h>#include <vector>using namespace std;// function to find Distance between// two closest minimumint findClosestMin(int arr[], int n){ int min = INT_MAX; // find the min element in the array for (int i = 0; i < n; i++) if (arr[i] < min) min = arr[i]; // vector to store indexes of occurrences // of minimum element in the array vector<int> indexes; // store indexes of occurrences // of minimum element in the array for (int i = 0; i < n; i++) if (arr[i] == min) indexes.push_back(i); // if minimum element doesnot occurs atleast // two times, return -1. if (indexes.size() < 2) return -1; int min_dist = INT_MAX; // calculate minimum difference between // any two consecutive indexes 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;}// Driver codeint 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
// Java program to find Distance between// two closest minimumimport java.util.Vector;class GFG {// function to find Distance between// two closest minimum static int findClosestMin(int arr[], int n) { int min = Integer.MAX_VALUE; // find the min element in the array for (int i = 0; i < n; i++) { if (arr[i] < min) { min = arr[i]; } } // vector to store indexes of occurrences // of minimum element in the array Vector<Integer> indexes = new Vector<>(); // store indexes of occurrences // of minimum element in the array for (int i = 0; i < n; i++) { if (arr[i] == min) { indexes.add(i); } } // if minimum element doesnot occurs atleast // two times, return -1. if (indexes.size() < 2) { return -1; } int min_dist = Integer.MAX_VALUE; // calculate minimum difference between // any two consecutive indexes 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; }// Driver code 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)); }}// This code is contributed by PrinciRaj19992 |
Python3
# Python3 program to find Distance # between two closest minimumimport sys # function to find Distance between# two closest minimumdef findClosestMin(arr, n): #assigning maximum value in python min = sys.maxsize for i in range(0, n): if (arr[i] < min): min = arr[i] # list in python to store indexes # of occurrences of minimum element # in the array indexes = [] # store indexes of occurrences # of minimum element in the array for i in range(0, n): if (arr[i] == min): indexes.append(i) # if minimum element doesnot occurs # atleast two times, return -1. if (len(indexes) < 2): return -1 min_dist = sys.maxsize # calculate minimum difference between # any two consecutive indexes 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;# Driver codearr = [ 5, 1, 2, 3, 4, 1, 2, 1 ]ans = findClosestMin(arr, 8)print (ans)# This code is contributed by saloni1297. |
C#
// C# program to find Distance between// two closest minimumusing System;using System.Collections.Generic;public class GFG { // function to find Distance between// two closest minimum static int findClosestMin(int []arr, int n) { int min = int.MaxValue; // find the min element in the array for (int i = 0; i < n; i++) { if (arr[i] < min) { min = arr[i]; } } // vector to store indexes of occurrences // of minimum element in the array List<int> indexes = new List<int>(); // store indexes of occurrences // of minimum element in the array for (int i = 0; i < n; i++) { if (arr[i] == min) { indexes.Add(i); } } // if minimum element doesnot occurs atleast // two times, return -1. if (indexes.Count < 2) { return -1; } int min_dist = int.MaxValue; // calculate minimum difference between // any two consecutive indexes 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; } // Driver code public static void Main() { int []arr = {5, 1, 2, 3, 4, 1, 2, 1}; int size = arr.Length; Console.WriteLine(findClosestMin(arr, size)); }} // This code is contributed by PrinciRaj19992 |
PHP
<?php// Php program to find Distance between // two closest minimum // function to find Distance between // two closest minimum 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]; // vector to store indexes of occurrences // of minimum element in the array $indexes = array() ; // store indexes of occurrences // of minimum element in the array for ($i = 0; $i < $n; $i++) if ($arr[$i] == $min) array_push($indexes, $i); // if minimum element doesnot occurs atleast // two times, return -1. if (sizeof($indexes) < 2) return -1; $min_dist = PHP_INT_MAX; // calculate minimum difference between // any two consecutive indexes 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; } // Driver code $arr = array( 5, 1, 2, 3, 4, 1, 2, 1 );$size = sizeof($arr); echo findClosestMin($arr, $size); // This code is contributed by Ryuga?> |
Javascript
<script> // Javascript program to find Distance between two closest minimum // function to find Distance between // two closest minimum function findClosestMin(arr, n) { let min = Number.MAX_VALUE; // find the min element in the array for (let i = 0; i < n; i++) { if (arr[i] < min) { min = arr[i]; } } // vector to store indexes of occurrences // of minimum element in the array let indexes = []; // store indexes of occurrences // of minimum element in the array for (let i = 0; i < n; i++) { if (arr[i] == min) { indexes.push(i); } } // if minimum element doesnot occurs atleast // two times, return -1. if (indexes.length < 2) { return -1; } let min_dist = Number.MAX_VALUE; // calculate minimum difference between // any two consecutive indexes 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)); // This code is contributed by suresh07.</script> |
Output
2
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
