Why A, B, C, D has the same length make the problem easier?


  • 0
    A

    The problem said A, B, C, D has the same length make the problem easier. I don't understand why. Could anyone tell me that.


  • 0
    S

    @aaa45190 This is valid question, looks like nobody is using this hint to make the solution better than O(n^2), let me think more to come up with better solution


  • 1
    L

    In my humble opinion, If there is no this restriction, some guys may fall into struggle with how to combine those arrays which is not the main meat of this problem. Let's assume the lengths of A,B,C,D are a,b,c,d, we should compute those three possible combination: max(ab, cd), max(ac, bd), max(ad, bc) at the beginning. For example, a=10000,b=10000,c=10,d=10. the time complex will be 10000x10000 if you choose max(ab, cd) while 10000x10 if you choose max(ac, bd).


  • 0

    @aaa45190 I posted a detailed analysis with proof for generic list sizes. It is a lot trickier if all 4 lists have different sizes, but the goal is to always balance time costs between building hashmap and loop-up for sum matching. Basically, it involves how to minimum function

    • f(x) = max(x, 1/x) for x > 0.

  • 0

    @lvjianchun You are right, but there are more than 2+2 split. We could build hashmap with only a single list or 3 lists as well depending on their list sizes. If 4 sizes are a <= b <= c <= d, actually there will be exactly two splits (ad, bc) or (abc, d) being the candidates for optimal time complexity. (Note: it could be abc <= d)

    I posted a detailed analysis with proof for generic list sizes.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.