Question2 Given a non-sorted array A of n integers and an integer value >x a) Si

Question

Question2 Given a non-sorted array A of n integers and an integer value >x a) Similar to Question 1, develop well-documented pseudo code that finds all pairs of elements of the array that subtract to exactly to | x |. The code however must be different than the one you had in Question 1 and must use either a stack S or a queue Q to perform what is needed. b) Briefly justify the motive(s) behind your design. c) d) e) What is the Big-O complexity of your solution? Explain clearly how you obtained such complexity What is the Big-2 complexity of your solution? Explain clearly how you obtained such complexity What is the Big-O space complexity of the utilized stack or queue? Explain your answer

Explanation / Answer

printPairs(A[], ar_size, x)

1) Sort the array in non-decreasing order.

2) Create two stack:

stack1 and stack2

3) Find middle of the array

middle = (ar_size/2)

3) Put first half of elements from array to first stack from first to middle

for i =1 to middle

stack1.push(A[i])

4) Put last half of elements from array to second stack from last to middle+1

for i =middle+1 to ar_size

stack2.push(A[i])

2) while stack1.notEmpty and stack2.nonEmpty

int a = stack1.top()

int b = stack2.top()

if(x == |a-b|) // if we got a pair

prinnt x and y

stack1.pop()

stack2.pop()

else if |a-b| > x // remove top elment from stack2

stack2.pop()

else

stack1.pop()

Since we need to find all pairs where difference if x, so I first sorted that array

Now putting half of the sorted elements in one stack and putting next half in the second stack

Now we find difference between smallest and largest elements, if difference is equal to x, then we founf the pair and remove from both stack. If difference is greater than x, then we remove top element of stack 2 so that we get lesser number from stack2 and hence next time difference will be greater

TIme Complexity:

Sorting: O(nlog)

Stack comparison: O(n)

So, overall: O(nlogn)

also in best case (all elements are already sorted), it takes O(nlogn) time to sort

so Omega(nlogn)

Space Complexity:

Since we are using stack size equsl to number of elements, hence = O(n)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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