PurpleThinker's blog

By PurpleThinker, 7 months ago, In English

A few days ago, someone much smarter than me shared with me the following problem. He said it involves "nothing else but simple arrays and for-loops, but has some weird observations to make". I couldn't solve it, even though the solution is simple enough that it can probably be understood by higher-rated pupils on CF. I thought it might be interesting to you, so here it is:

You are given an array $$$a$$$ with $$$n$$$ positive integers (you don't know anything about their maximum value). Find out the maximum difference between two elements if the array $$$a$$$ would be sorted.

Example:
Input: $$$n = 4, a = [11, 2, 7, 5]$$$
Output: $$$4$$$, because if we were to sort the array $$$a$$$, then we would have $$$[2, 5, 7, 11]$$$, so the maximum difference between two adjacent elements is $$$4$$$.

Of course, you can just sort the array in $$$O(n \log n)$$$ and find the difference that way. Value-based sorting (like radix sort) is not an option because you don't know what the maximum value is. But there is actually a way to find it in $$$O(n)$$$, without sorting the array.

Hint
Solution

Hope you enjoyed the problem!

  • Vote: I like it
  • +274
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +154 Vote: I do not like it

Cool! Now find minimum. Seriously though.

Hint
Solution
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +91 Vote: I do not like it
    The cool thing about it
    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it
      Spoiler
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        I get the joke, but I can't just let it slide. The whole point is that it is $$$O(n)$$$.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Here is fun algorithm for finding 2 closest points on 2D plane:

      1. sort all the points alongside random direction (by dot product with randomly chosen vector)

      2. check all the pairs of neighbors (in that order)

      3. repeat with new random vectors additional 5 (or 10 if you get WA) times

      Yeah, technically it is $$$O(n \log n)$$$ but it is significantly faster in practice.

      And coding only takes a few minutes.

      It does not generalize to higher dimensions though.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

nice problem

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    it is wrong, think harder.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      spitting this nonsense. I'm not if he used even a 1% of his brain power.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      You probably just implemented it wrong lmao

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sorry, I don't see how that solution is correct.

        a = [5 2 1 4] sorted_a = [1 2 4 5] max = 5 second_max = 4 diff = 1 max_diff = 2 ???

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    found the guessforces expert

»
6 months ago, # |
  Vote: I like it +54 Vote: I do not like it

A mandatory pedantic comment

Value-based sorting (like radix sort) is not an option because you don't know what the maximum value is

This is a horrible way to phrase it because you immediately proceed to contradict yourself:

I will call max the maximum value in a ... You can calculate these in O(n) time

Maybe you wanted to say that the radix sort has a pseudopolynomial complexity? However, this is not true, because its complexity is O(wn), where n is the number of keys, and w is the key length. It is polynomial because the input size is also O(wn).

Maybe you wanted to say that w is large, in which case O(wn) is polynomial but slow? However, your proposed solution also becomes slow if you account for the increasing cost of arithmetic operations. For example, subtraction becomes O(w), and division by n-1 may be even slower.

Maybe it's possible to construct a computational system where the complexities of primitive operations work out in favor of your proposed solution, but I doubt that it will be practical.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I think for $$$a_i \le 10^9,$$$ we can assume that the cost of such arithmetic operations is basically constant (because of word size), but it is not feasible to create an array of size $$$10^9$$$ in order to perform radix sort.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      You can radix sort by the first bit, then by the second bit, etc. This way, you can sort 32-bit integers in 32 linear-time passes. (or be smarter and do 4 passes, each sorting by a group of 8 bits)

      In general, you can sort $$$N$$$ numbers of $$$W$$$ bits in $$$O(WN)$$$ time.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        I see. For some reason, I mistook radix sort for counting sort. 🤡

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You must be thinking about counting sort, not radix sort.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +37 Vote: I do not like it

        Yes, I realized that later. I'm a clown

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    For me, it was pretty clear that he meant that you don't know the maximum value at the time of writing the program.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As if someone hardcodes key length in radix sort.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, radix sort wouldn't be significantly slower even with big numbers, but still. I agree with the things you said, but trying out both versions and measuring their runtime have more worth than talking about them.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I don’t think so.

      Spoiler
»
6 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Cool problem! I think there is a small mistake in your explanation.

explanation
»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

' with n positive integers (you don't know anything about their maximum value'

' I will call max the maximum value in a and min -- the minimum value. You can calculate these in O(n) time'

Totally not contradictory.

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

numbers within the same bucket: calculate max value — min value from the bucket

isn't this both not correct and unnecessary?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree, if the lower bound is the box size you never need to consider 2 elements from the same box. Also it would only be a valid candidate if the number of elements in the box were exactly 2.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this?

Value-based sorting (like radix sort) is not an option because you don't know what the maximum value is.

If you read the input array, you will definitely know the maximum value.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    They are saying that it can be really large, so you can't use radix sort, because it takes $$$\mathcal{O(n \cdot \ell)}$$$. But as described in nskybytskyi's comment above, if the numbers are really quite large, the comparision and division operations described in this solution take $$$\mathcal{O(\ell)}$$$ time anyway (where $$$\ell$$$ is the length of the binary representation of the number).

»
6 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

What about using a vector containing ints (or lls) called values? Then, as you traverse the elements of the input array, you can set values[index]=value. Then, couldn't you just loop through 0 to n-1, and find the maximum value of the absolute value of (values[index+1]-values[index]), and output the max? Please let me know if I misunderstood the problem.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah you definitely did, the problem is asking about max adjacent difference in a sorted array