Question

In: Accounting

Finding the complexity of Finding the largest two elements in a queue of size n+3 using...

Finding the complexity of Finding the largest two elements in a queue of size n+3 using Naïve search. with explain

Solutions

Expert Solution

Please mentioned below the answer

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is a concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

Naive implementations

There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is. For instance, one can keep all the elements in an unsorted list. Whenever the highest-priority element is requested, search through all elements for the one with the highest priority. (In big O notation: O(1) insertion time, O(n) pull time due to search.)

Naive approach: Use 2 loops. Check each element in the array with all other elements in the array and keep track of its count and also maintain the max counter which track the element repeats the maximum number of time.

Time Complexity : O(n^2) Space Complexity: O(1)

Code :

 public class MaxRepeatingBruteForce {
     public void MaxRepeatingElement(int [] arrA){
         int maxCounter = 0;
         int element=0;
         for (int i = 0; i <arrA.length ; i++) {
             int counter =1;
             for (int j = i+1; j <arrA.length ; j++) {
                 if(arrA[i]==arrA[j]){
                     counter++;
                 }
             }
             if(maxCounter<counter){
                 maxCounter=counter;
                 element = arrA[i];
             }
         }
         System.out.println("Element repeating maximum no of times: " + element + ", maximum count: " + maxCounter);
     }
  
     public static void main(String[] args) {
      int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7};
      MaxRepeatingBruteForce m = new MaxRepeatingBruteForce();
      m.MaxRepeatingElement(arrA);
     }
 }

Sorting approach: Sort the array, this will bring all the duplicates together if present. Now navigate the array and keep track of its count and also maintain the max counter which track the element repeats the maximum number of time.

Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.

Code:

 import java.util.Arrays;
  
 public class MaxRepeatingUsingSorting {
     public void maxRepeatingElementUsingSorting(int [] arrA){
         if(arrA.length<1){
             System.out.println("Inavlid Array");
             return;
         }
         Arrays.sort(arrA);
         int count=1;
         int maxCount=1;
         int currentElement = arrA[0];
         int maxCountElement =arrA[0];
         for (int i = 1; i <arrA.length ; i++) {
             if(currentElement==arrA[i]){
                 count++;
             }else{
                 if(count>maxCount){
                     maxCount = count;
                     maxCountElement = currentElement;
                 }
                 currentElement = arrA[i];
                 count = 1;
             }
         }
         System.out.println("Element repeating maximum no of times: " + maxCountElement + ", maximum count: " + maxCount);
     }
     public static void main(String[] args) {
         int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7};
         MaxRepeatingUsingSorting m = new MaxRepeatingUsingSorting();
         m.maxRepeatingElementUsingSorting(arrA);
     }
 }

Better Solution (Conditional) : O(n) time and O(1) extra space.

§ This solution works only if array has positive integers and all the elements in the array are in range from 0 to n-1 where n is the size of the array.

§ Nav­i­gate the array.

§ Update the array as for ith index :- arrA[arrA[i]% n] = arrA[arrA[i]% n] + n;

§ Now navigate the updated array and check which index has the maximum value, that index number is the element which has the maximum occurrence in the array.

§ See the picture below for more explanation.

Similar approach used in problem : if array has all consecutive numbers.

public class MaxRepeatingElement {

    public void MaxRepeatingElementInPlace(int [] arrA){

        int size = arrA.length;

        int maxCount=0;

        int maxIndex=0;

        for (int i = 0; i <size ; i++) {

            //get the index to be updated

            int index = arrA[i]% size;

            arrA[index] = arrA[index] + size;

        }

        for (int i = 0; i <size ; i++) {

            if(arrA[i]/size>maxCount){

                maxCount=arrA[i]/size;

                maxIndex=i;

            }

        }

        System.out.println("Element repeating maximum no of times: " + maxIndex + ", maximum count: " + maxCount);

    }

  public static void main(String[] args) {

        int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7};

        MaxRepeatingElement m = new MaxRepeatingElement();

        m.MaxRepeatingElementInPlace(arrA);

    }

}


Related Solutions

Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements....
Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in...
Using a single queue (linkedQueue), re-implement the concept of Stack ADT, what is the complexity of...
Using a single queue (linkedQueue), re-implement the concept of Stack ADT, what is the complexity of the method push, pop, top, isEmpty, and size. You should not use any extra data structure. Related codes: public interface Stack<E> { int size( ); boolean isEmpty( ); void push(E e); E top( ); E pop( ); } public class LinkedStack<E> implements Stack<E> { private SinglyLinkedList<E> list = new SinglyLinkedList<>( );    public LinkedStack( ) { }    public int size( ) { return...
Given an unsorted integer array A of size n, develop an pseudocode with time complexity as...
Given an unsorted integer array A of size n, develop an pseudocode with time complexity as low as possible to find two indexes i and j such that A[i] + A[j] = 100. Indexes i and j may or may not be the same value.
Characteristics of an ANOVA (for both one-way and repeated measure) Finding df Finding sample size(n) from...
Characteristics of an ANOVA (for both one-way and repeated measure) Finding df Finding sample size(n) from df Finding sample size(N) from df Characteristics of a f-distribution N vs n What affects the size of your f-ratio What is MS Correlation meaning of calculation interpretation SP FREE RESPONSE Questions Calculating an ANOVA (such as finding df, SS, MS, etc) Interpreting SPSS output MORE calculating an ANOVA Correlation APA formatting - This is a study guide for my statistics final and I...
What is the largest size n of a problem that can solve in 1 second, assuming...
What is the largest size n of a problem that can solve in 1 second, assuming that the algorithm to solve the problem takes sqrt(n) microseconds? (sqrt stands for square root) 1 10^(6) 10^(12) 10^(3) How does the array arr = [8, 5, 3, 6, 10] look like after the second iteration (when j = 3) of the j loop on line 1 of the give pseudocode below? insertion_sort.PNG 1 for j 2 do 3 // Insert A[j] into the...
Assume you have a stack and a queue implemented using an array of size 4. show...
Assume you have a stack and a queue implemented using an array of size 4. show the content of the array for the stack (then the queue) for the following operations: (for the queue replace push by add and pop by remove; keep in mind that the queue uses a circular array): push(-3), push(-5), push(-9), push(-10), pop(), pop(), push(-13), pop(), push( -15), push(-17). java code
Two stacks are the same if they have the same size and their elements at the...
Two stacks are the same if they have the same size and their elements at the corresponding positions are the same. Add the method equalStack to class ArrayStack that takes as a parameter ArrayStack object otherStack, and returns true if this stack is the same as otherStack. Use the following signature for your method: public boolean equalStack(ArrayStack otherStack) { ... }
C++ Consider the following algorithm for finding the distance between the two closest elements in an...
C++ Consider the following algorithm for finding the distance between the two closest elements in an array of numbers. ALGORITHM MinDistance(A[0..n − 1]) //Input: Array A[0..n − 1] of numbers //Output: Minimum distance between two of its elements dmin←∞ for i ←0 to n − 1 do for j ←0 to n − 1 do if i ≠ j and |A[i]− A[j ]| < dmin dmin ←|A[i]− A[j ]| return dmin Make as many improvements as you can in this...
3. Suppose we want to find the 2nd largest and 2nd smallest elements simultaneously for an...
3. Suppose we want to find the 2nd largest and 2nd smallest elements simultaneously for an input of n numbers stored in an array A[1:n]. Compare the following strategies in terms of their exact number of comparisons. Strategy 1: adapt the two separate For loops idea for minimum and maximum. Strategy 2: Run mergesort to sort the numbers in ascending or descending order, then output the 2nd ranked and (n-1)th ranked elements. First write each algorithm in pseudocde, then analyze...
C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10...
C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT