Given an array arr[] of N integers, the task is to find the minimum possible absolute difference between indices of a special pair.
A special pair is defined as a pair of indices (i, j) such that if arr[i] ? arr[j], then there is no element X (where arr[i] < X < arr[j]) present in between indices i and j.
For example:
arr[] = {1, -5, 5}
Here, {1, 5} forms a special pair as there are no elements in the range (1 to 5) in between arr[0] and arr[2].
Print the minimum absolute difference abs(j – i) such that pair (i, j) forms a special pair.
Examples:
Input: arr[] = {0, -10, 5, -5, 1}
Output: 2
Explanation:
The elements 1 and 5 forms a special pair since there is no elements X in the range 1 < X < 5 in between them, and they are 2 indices away from each other.
Input: arr[] = {3, 3}
Output: 1
Naive Approach: The simplest approach is to consider every pair of elements of the array and check if they form a special pair or not. If found to be true, then print the minimum distance among all the pairs formed.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to observe that we have to only consider the distance between the position of adjacent elements in the sorted array since those pair of elements will not have any value X between it. Below are the steps:
- Store the initial indices of array elements in a Map.
- Sort the given array arr[].
- Now, find the distance between the indices of adjacent elements of the sorted array using the Map.
- Maintain the minimum distance for each pair of adjacent elements in the step above.
- After the completing the above steps, print the minimum distance formed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std;// Function that finds the minimum // difference between two vectorsint mindist(vector<int>& left, vector<int>& right) { int res = INT_MAX; for (int i = 0; i < left.size(); ++i) { int num = left[i]; // Find lower bound of the index int index = lower_bound(right.begin(), right.end(), num) - right.begin(); // Find two adjacent indices // to take difference if (index == 0) res = min(res, abs(num - right[index])); else if (index == right.size()) res = min(res, abs(num - right[index - 1])); else res = min(res, min(abs(num - right[index - 1]), abs(num - right[index]))); } // Return the result return res; } // Function to find the minimum distance // between index of special pairs int specialPairs(vector<int>& nums) { // Stores the index of each element // in the array arr[] map<int, set<int> > m; vector<int> vals; // Store the indexes for (int i = 0; i < nums.size(); ++i) { m[nums[i]].insert(i); } // Get the unique values in list for (auto p : m) { vals.push_back(p.first); } int res = INT_MAX; for (int i = 0; i < vals.size(); ++i) { vector<int> vec(m[vals[i]].begin(), m[vals[i]].end()); // Take adjacent difference // of same values for (int i = 1; i < vec.size(); ++i) res = min(res, abs(vec[i] - vec[i - 1])); if (i) { int a = vals[i]; // Left index array vector<int> left(m[a].begin(), m[a].end()); int b = vals[i - 1]; // Right index array vector<int> right(m[b].begin(), m[b].end()); // Find the minimum gap between // the two adjacent different // values res = min(res, mindist(left, right)); } } return res; } // Driver Code int main() { // Given array vector<int> arr{ 0, -10, 5, -5, 1 }; // Function Call cout << specialPairs(arr); return 0; } |
Java
// Java program for the above approachimport java.util.*;class Main { // Function that finds the minimum // difference between two vectors public static int Mindist(List<Integer> left, List<Integer> right) { int res = Integer.MAX_VALUE; for (int i = 0; i < left.size(); i++) { int num = left.get(i); // Find lower bound of the index int index = right.indexOf(right.stream().filter(x -> x <= num).findFirst().orElse(right.get(right.size() - 1))); // Find two adjacent indices // to take difference if (index == 0) { res = Math.min(res, Math.abs(num - right.get(index))); } else if (index == right.size()) { res = Math.min( res, Math.min( Math.abs(num - right.get(index - 1)), Math.abs(num - right.get(index)) ) ); } } // Return the result return res; } // Function to find the minimum distance // between index of special pairs public static int SpecialPairs(int[] nums) { // Stores the index of each element // in the array arr[] Map<Integer, Integer> m = new HashMap<Integer, Integer>(); List<Integer> vals = new ArrayList<Integer>(); for (int i = 0; i < nums.length; i++) { m.put(nums[i], i); } for (int p : m.keySet()) { vals.add(p); } int res = Integer.MAX_VALUE; for (int i = 1; i < vals.size(); i++) { List<Integer> vec = new ArrayList<Integer>(); vec.add(m.get(vals.get(i))); // Take adjacent difference // of same values for (int j = 1; j < vec.size(); j++) { res = Math.min(res, Math.abs(vec.get(j) - vec.get(j - 1))); } if (i > 0) { int a = vals.get(i); // Left index array List<Integer> left = new ArrayList<Integer>(); left.add(m.get(a)); int b = vals.get(i - 1); // Right index array List<Integer> right = new ArrayList<Integer>(); right.add(m.get(b)); // Find the minimum gap between // the two adjacent different // values res = Math.min(res, Mindist(left, right)) + 1; } } return res; } // Driver Code public static void main(String[] args) { int[] arr = {0, -10, 5, -5, 1}; System.out.println(SpecialPairs(arr)); }}// This code is contributed by princekumaras |
Python3
# Python3 program for the above approachimport sys# Function that finds the minimum# difference between two vectorsdef mindist(left, right): res = sys.maxsize for i in range(len(left)): num = left[i] # Find lower bound of the index index = right.index(min( [i for i in right if num >= i])) # Find two adjacent indices # to take difference if (index == 0): res = min(res, abs(num - right[index])) elif (index == len(right)): res = min(res, min(abs(num - right[index -1]), abs(num - right[index]))) # Return the result return res # Function to find the minimum distance# between index of special pairsdef specialPairs(nums): # Stores the index of each element # in the array arr[] m = {} vals = [] for i in range(len(nums)): m[nums[i]] = i for p in m: vals.append(p) res = sys.maxsize for i in range(1, len(vals)): vec = [m[vals[i]]] # Take adjacent difference # of same values for i in range(1, len(vec)): res = min(res, abs(vec[i] - vec[i - 1])) if (i): a = vals[i] # Left index array left = [m[a]] b = vals[i - 1] # Right index array right = [m[b]] # Find the minimum gap between # the two adjacent different # values res = min(res, mindist(left, right)) + 1 return res# Driver Codeif __name__ == "__main__": # Given array arr = [ 0, -10, 5, -5, 1 ] # Function call print(specialPairs(arr))# This code is contributed by dadi madhav |
Javascript
// Function that finds the minimum// difference between two vectorsfunction mindist(left, right) { let res = Number.MAX_SAFE_INTEGER; for (let i = 0; i < left.length; i++) { const num = left[i]; // Find lower bound of the index const index = right.findIndex((i) => num >= i); // Find two adjacent indices // to take difference if (index === 0) { res = Math.min(res, Math.abs(num - right[index])); } else if (index === right.length) { res = Math.min( res, Math.min( Math.abs(num - right[index - 1]), Math.abs(num - right[index]) ) ); } } // Return the result return res;}// Function to find the minimum distance// between index of special pairsfunction specialPairs(nums) { // Stores the index of each element // in the array arr[] const m = new Map(); const vals = []; for (let i = 0; i < nums.length; i++) { m.set(nums[i], i); } for (const p of m.keys()) { vals.push(p); } let res = Number.MAX_SAFE_INTEGER; for (let i = 1; i < vals.length; i++) { const vec = [m.get(vals[i])]; // Take adjacent difference // of same values for (let j = 1; j < vec.length; j++) { res = Math.min(res, Math.abs(vec[j] - vec[j - 1])); } if (i) { const a = vals[i]; // Left index array const left = [m.get(a)]; const b = vals[i - 1]; // Right index array const right = [m.get(b)]; // Find the minimum gap between // the two adjacent different // values res = Math.min(res, mindist(left, right)) + 1; } } return res;}// Driver Codeconst arr = [0, -10, 5, -5, 1];console.log(specialPairs(arr));// This code is contributed by Aditya Sharma |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { // Function that finds the minimum // difference between two vectors static int mindist(List<int> left, List<int> right) { int res = int.MaxValue; for (int i = 0; i < left.Count; i++) { int num = left[i]; // Find lower bound of the index int index = right.IndexOf( right.Where(i = > num >= i).Min()); // Find two adjacent indices // to take difference if (index == 0) res = Math.Min( res, Math.Abs(num - right[index])); else if (index == right.Count) res = Math.Min( res, Math.Min( Math.Abs(num - right[index - 1]), Math.Abs(num - right[index]))); } // Return the result return res; } // Function to find the minimum distance // between index of special pairs static int specialPairs(List<int> nums) { // Stores the index of each element // in the array arr[] Dictionary<int, int> m = new Dictionary<int, int>(); List<int> vals = new List<int>(); for (int i = 0; i < nums.Count; i++) m[nums[i]] = i; vals = m.Keys.ToList(); int res = int.MaxValue; for (int i = 1; i < vals.Count; i++) { List<int> vec = new List<int>(); vec.Add(m[vals[i]]); // Take adjacent difference // of same values for (int j = 1; j < vec.Count; j++) res = Math.Min( res, Math.Abs(vec[j] - vec[j - 1])); if (i > 0) { int a = vals[i]; // Left index array List<int> left = new List<int>(); left.Add(m[a]); int b = vals[i - 1]; // Right index array List<int> right = new List<int>(); right.Add(m[b]); // Find the minimum gap between // the two adjacent different // values res = Math.Min(res, mindist(left, right)) + 1; } } return res; } static void Main(string[] args) { // Given array List<int> arr = new List<int>() { 0, -10, 5, -5, 1 }; // Function call Console.Write(specialPairs(arr)); }}// This code is contributed by Prince Kumar |
Output:
2
Time Complexity: O(N*log N)
Auxiliary Space: O(N) , since N extra space has been taken.
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!
