CODEWITHSUNDEEP
arraysoptimizationdata-structuresarray-difference
Ann
Ann

Reputation: 53

I need help in optimization of an array problem that has been asked in interview last month

Given 2 arrays a and b find the max value of b[i] + b[j] + b[k] (i !=j != k) , where the following condition is satisfied a[i] > a[j] > a[k]

I can calculate it by using 3 loops. I have been asked to optimize the problem during the interview but was unable to do it. any optimized method better than O(n^3) ? thanks

Upvotes: 0

Views: 160

Answers (1)

Welbog
Welbog

Reputation: 60448

You can probably get away with an O(n log n) solution by sorting B (n log n time) and tracking which indexes are used, checking A for the property A[i] > A[j] > A[k]. Note that since the only relationship between i, j and k is that they are not equal, their order doesn't seem to matter. (Also, it might be that i and k can be equal, but we'll ignore that for now.)

Pseudocode:

function findSum(A, B):
  declare array B_with_index
 
  // O(n)
  for index 0 to |B|-1:
    insert (B[index], index) into B_with_index

  // O(n log n)
  sort B_with_index by its first value, descending

  // O(n)
  for index 0 to |B|-3:
    b_1 := B_with_index[index]
    b_2 := B_with_index[index+1]
    b_3 := B_with_index[index+2]

    // Note that we're only checking for inequality here
    // This is because i, j and k have no relationship
    // other than inequality. E.q., if A[i] < A[j], we can
    // just swap the definitions of i and j.
    if A[b_1.index] != A[b_2.index] and A[b_2.index] != A[b_3.index] then
      return b_1.value + b_2.value + b_3.value

  return error

This relies on the fact that if you sort an array such as [1, 5, 25, 2, -5, 50], the maximum sum will be at the start: [50, 25, 5, 2, 1, -5]. Then all you have to do is make sure the indexes involved have the right property within A.

Upvotes: 1

Related Questions