Hi, I need some help with this Data Structures and Algorithms Analysis question.

Question

Hi, I need some help with this Data Structures and Algorithms Analysis question.

Let A[1.nl be an array with n elements, where n 1, Assume that AIile {1, 2, 3, 4, 5, 6, 7, 8 9} for all i = 1, 2, n. Write an algorithm using pseudocode that finds the first non-repeated value on the array. Return the index of the first non-repeated value. If no such value exists, then return -1. The running time of the algorithm must be O(n). Here are some examples: if A-$9,7,4,1,7,9, then the first non-repeated value is "4" so the algorithms returns 3 if A = , then the algorithm returns-1 because all the values are repeated.

Explanation / Answer

We need to find the first non repeating value's index. Let's build a count array first. Count array stores the count of number of occurances of an element in a single loop.
count[MAX] where MAX is the maximum element in the array
for i in range(1,n)
   count[A[i]]++ //Incrementing the count of the value A[i]

After we have the count array, which stores the count of occurances of element in the array, we just need to find the first value whose count is 1. That means there are no other duplicate elements.

FUNCTION FIRST_NON_REPEATED(INT ARR[], INT N)
   //Initialize array for count
   INT COUNT[N}
   COUNT[1 to N] = 0
   //Iterate through all the elements and fill count array
   FOR I IN RANGE(0,N)  
       COUNT[ARR[I]]++
   ANS = -1
   //Iterate through all the elements in the array and return the first index whose count is 1
   FOR I IN RANGE(0,N)
       IF COUNT[A[i]]==1
           RETURN I
   RETURN ANS
END FUNCTION

In the algorithm we have 2 loops which iterate through all the elements in the array. So, time complexity is O(N) + O(N) = O(2*N) = O(N)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.