Horje
Minimum operations to make Array distinct by deleting and appending on opposite ends

Given an array arr[] of N integers. the task is to find the minimum number of operations required to make all the elements of the array distinct using the following operations. 

  • Remove one element from the starting of the array arr[] and append any integer to the end.
  • Remove one element from the end of the array arr[] and prepend any integer to the beginning.

Examples:

Input: arr[] = {1, 3, 3, 5, 1, 9, 4, 1}
Output: 4
Explanation: Remove 1 from end and add 5 at starting [5, 1, 3, 3, 5, 1, 9, 4]
Remove 5 from start and add 7 at end [1, 3, 3, 5, 1, 9, 4, 7]
Remove 1 from start and add 8 at end [3, 3, 5, 1, 9, 4, 7, 8]
Remove 3 from start and add 2 at end [3, 5, 1, 9, 4, 7, 8, 2]

Input: arr[] = {1, 2, 3, 5, 4}
Output: 0

 

Approach: To solve the problem follow the below idea and steps:

  • At first, find the subarray containing all unique character and store its starting index at i and ending index at j,
  • Now, apply the formula 2*min(i, N – j – 1) + max(i, N – j – 1) and return the answer,  
  • Why the formula works? 
    • As, we have to remove the elements from start to i and from j to end, so choose which is minimum, then add twice of that with the maximum. 
  • There is an edge case, where the multiple max size subarray come then give the preference to that subarray whose starting index is 0 or ending index is 
    N-1.

Follow the steps mentioned below to solve the problem:

  • First, find the Max size subarray of all unique characters.
  • Find the pair {i, j} i.e., the index of the first and last element of the desired subarray respectively.
  • Apply the formula,  2*min(i, N – j – 1) + max(i, N – j – 1) and return it as the answer.

Below is the implementation of the above approach:

C++

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find max subarray
// with all unique characters
pair<int, int> findMax(int a[], int n)
{
    unordered_map<int, int> index;
    int ans = 0, x = -1, y = -1;
 
    for (int i = 0, j = 0; i < n; i++) {
        j = max(index[a[i]], j);
        if ((i - j + 1) >= ans) {
 
            // If there are multiple
            // max subarray
            if ((i - j + 1) == ans) {
 
                // If the subarray is touching
                // the edge of the array
                if (i == (n - 1) || j == 0) {
                    ans = i - j + 1;
                    x = i;
                    y = j;
                }
            }
 
            // If there is new max subarray
            else {
                ans = i - j + 1;
                x = i;
                y = j;
            }
        }
        index[a[i]] = i + 1;
    }
 
    // Return the starting and ending indices
    // of max size subarray
    return { x, y };
}
 
// Function to find minimum operations
// to make all the characters of arr unique
int findMinOperations(int* arr, int n)
{
    pair<int, int> p = findMax(arr, n);
 
    int i = p.second;
    int j = p.first;
 
    return 2 * min(i, n - j - 1)
           + max(i, n - j - 1);
}
 
// Drivers code
int main()
{
    int arr[] = { 1, 3, 3, 5, 1, 9, 4, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << findMinOperations(arr, N);
    return 0;
}

Java

// Java code to implement the above approach
 
import java.io.*;
import java.util.*;
 
class pair {
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG {
 
    // Function to find max subarray with all unique
    // characters.
    public static pair findMax(int[] a, int n)
    {
        HashMap<Integer, Integer> index
            = new HashMap<Integer, Integer>();
        int ans = 0, x = -1, y = -1;
        for (int i = 0, j = 0; i < n; i++) {
            if (index.get(a[i]) != null) {
                j = Math.max(index.get(a[i]), j);
            }
            if ((i - j + 1) >= ans) {
                // If there are multiple max subarray
                if ((i - j + 1) == ans) {
                    // If the subarray is touching the edge
                    // of the array
                    if (i == (n - 1) || j == 0) {
                        ans = i - j + 1;
                        x = i;
                        y = j;
                    }
                }
                // If there is new max subarray
                else {
                    ans = i - j + 1;
                    x = i;
                    y = j;
                }
            }
            index.put(a[i], i + 1);
        }
        // Return the starting and ending indices of max
        // size subarray
        return new pair(x, y);
    }
 
    // Function to find minimum operations to make all the
    // characters of arr unique
    public static int findMinOperations(int[] arr, int n)
    {
        pair p = findMax(arr, n);
        int i = p.second;
        int j = p.first;
        return 2 * Math.min(i, n - j - 1)
            + Math.max(i, n - j - 1);
    }
 
    public static void main(String[] args)
    {
 
        int[] arr = { 1, 3, 3, 5, 1, 9, 4, 1 };
        int N = arr.length;
 
        // Function call
        System.out.print(findMinOperations(arr, N));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

Python3

# Python code to implement the above approach
 
# Function to find max subarray
# with all unique characters
def findMax(a, n):
    index = {}
    ans = 0
    x = -1
    y = -1
    j = 0
    for i in range(n):
        if a[i] in index:
            j = max(index[a[i]], j)
        if ((i - j + 1) >= ans):
           
            # If there are multiple
            # max subarray
            if ((i - j + 1) == ans):
               
                # If the subarray is touching
                # the edge of the array
                if (i == (n - 1) or j == 0):
                    ans = i - j + 1
                    x = i
                    y = j
 
            # If there is new max subarray
            else:
                ans = i - j + 1
                x = i
                y = j
        index[a[i]] = i + 1
 
    # Return the starting and ending indices
    # of max size subarray
    return [x, y]
 
# Function to find minimum operations
# to make all the characters of arr unique
def findMinOperations(arr, n):
    p = findMax(arr, n)
    i = p[1]
    j = p[0]
 
    return 2 * min(i, n - j - 1) + max(i, n - j - 1)
 
# Drivers code
if __name__ == "__main__":
    arr = [1, 3, 3, 5, 1, 9, 4, 1]
    N = len(arr)
 
    # Function Call
    print(findMinOperations(arr, N))
 
# This code is contributed by Rohit Pradhan

C#

// C# code to implement the above approach
 
 
using System;
using System.Collections.Generic;
 
 
class pair {
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
public class GFG {
 
    // Function to find max subarray with all unique
    // characters.
    static pair findMax(int[] a, int n)
    {
        Dictionary<int, int> index
            = new Dictionary<int, int>();
        int ans = 0, x = -1, y = -1;
        for (int i = 0, j = 0; i < n; i++) {
            if (index.ContainsKey(a[i])) {
                j = Math.Max(index[a[i]], j);
            }
            if ((i - j + 1) >= ans) {
                // If there are multiple max subarray
                if ((i - j + 1) == ans) {
                    // If the subarray is touching the edge
                    // of the array
                    if (i == (n - 1) || j == 0) {
                        ans = i - j + 1;
                        x = i;
                        y = j;
                    }
                }
                // If there is new max subarray
                else {
                    ans = i - j + 1;
                    x = i;
                    y = j;
                }
            }
            if(index.ContainsKey(a[i]))
                index[a[i]] = i+1;
            else
                index.Add(a[i], i + 1);
        }
        // Return the starting and ending indices of max
        // size subarray
        return new pair(x, y);
    }
 
    // Function to find minimum operations to make all the
    // characters of arr unique
    public static int findMinOperations(int[] arr, int n)
    {
        pair p = findMax(arr, n);
        int i = p.second;
        int j = p.first;
        return 2 * Math.Min(i, n - j - 1)
            + Math.Max(i, n - j - 1);
    }
 
    public static void Main(String[] args)
    {
 
        int[] arr = { 1, 3, 3, 5, 1, 9, 4, 1 };
        int N = arr.Length;
 
        // Function call
        Console.Write(findMinOperations(arr, N));
    }
}
 
 
// This code contributed by shikhasingrajput

Javascript

<script>
    // JavaScript code to implement the above approach
 
    // Function to find max subarray
    // with all unique characters
    const findMax = (a, n) => {
        let index = {};
        let ans = 0, x = -1, y = -1;
 
        for (let i = 0, j = 0; i < n; i++) {
            j = Math.max(a[i] in index ? index[a[i]] : 0, j);
            if ((i - j + 1) >= ans) {
 
                // If there are multiple
                // max subarray
                if ((i - j + 1) == ans) {
 
                    // If the subarray is touching
                    // the edge of the array
                    if (i == (n - 1) || j == 0) {
                        ans = i - j + 1;
                        x = i;
                        y = j;
                    }
                }
 
                // If there is new max subarray
                else {
                    ans = i - j + 1;
                    x = i;
                    y = j;
                }
            }
            index[a[i]] = i + 1;
        }
 
        // Return the starting and ending indices
        // of max size subarray
        return [x, y];
    }
 
    // Function to find minimum operations
    // to make all the characters of arr unique
    const findMinOperations = (arr, n) => {
        let p = findMax(arr, n);
 
        let i = p[1];
        let j = p[0];
        return 2 * Math.min(i, n - j - 1)
            + Math.max(i, n - j - 1);
    }
 
    // Drivers code
 
    let arr = [1, 3, 3, 5, 1, 9, 4, 1];
    let N = arr.length;
 
    // Function Call
    document.write(findMinOperations(arr, N));
 
    // This code is contributed by rakeshsahni
 
</script>

Output

4

Time Complexity: O(N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Last remaining element by removing values closest to half of Array sum Last remaining element by removing values closest to half of Array sum
Maximize M such that swapping arr[i] with arr[i+M] makes Array sorted Maximize M such that swapping arr[i] with arr[i+M] makes Array sorted
Check if all possible Triplet Sum is present in given Array Check if all possible Triplet Sum is present in given Array
Count of elements altering which changes the GCD of Array Count of elements altering which changes the GCD of Array
Permutation of first N elements with absolute adjacent difference in increasing order Permutation of first N elements with absolute adjacent difference in increasing order

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje