# Circles dividing the plane

You will be given a set of circles in the plane with their centers on the line y=0. It is guaranteed that no pair of circles has more than one common point.

Your task is to determine into how many regions into which the circles divide the plane. A region is an inclusion-maximal contiguous set of points not intersecting any of the circles.

You should write a program that computes this answer when given a description of the circles.

Here's an example:

On the left side you see the circles drawn in the plane. However, in the right half of the picture, the regions produced by the circles are colored distinctly (one color per region). There are six regions in this example.

### Input

The first line of the input contains a number, N, the number of circle descriptions to follow. This line is optional, if your solution works without it, it's fine.

The following N lines each contain two integers, xi and ri > 0, representing a circle with center (xi, 0) and radius ri.

It is guaranteed that no pair of circles has more than one common point. It is further guaranteed that xi and ri do not exceed 10^9 in absolute value (so they comfortably fit into a 32-bit integer).

The input may be:

• read from a file named I in the current directory

Alternatively, the input could be:

• available as a string (including newlines) in a global variable

• on the stack

### Output

This should be a single integer, the number to regions produced. This should be written to STDOUT or a file named O in the current directory.

### Rules

• Shortest code in bytes wins

• +200 byte penalty if your code does not have a runtime + space complexity polynomial in n

• -100 byte bonus for worst-case expected runtime + space complexity O(n log n)

• -50 byte bonus for worst-case expected runtime + space complexity O(n)

• -100 byte bonus for deterministic runtime + space complexity O(n)

While assessing the runtime:

• Assume that hash tables have O(1) expected runtime for insert, delete and lookup, regardless of the sequence of operations and the input data. This may or may not be true, depending on whether the implementation uses randomization.

• Assume that the builtin sort of your programming language takes deterministic O(n log n) time, where n is the size of the input sequence.

• Assume that arithmetic operations on input numbers take only O(1) time.

• Do not assume that input numbers are bound by a constant, although, for practical reasons, they are. This means that algorithms like radix sort or counting sort are not linear time. In general, very large constant factors should be avoided.

### Examples

Input:

2
1 3
5 1


Output: 3

Input:

3
2 2
1 1
3 1


Output: 5

4
7 5
-9 11
11 9
0 20


Input:

9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2


Output: 11

## Hints

We can use the following idea for a very compact solution. Lets intersect the set of circles with the X axis and interpret the intersection points as nodes in a planar graph:

Every circle produces exactly 2 edges in this graph and up to two nodes. We can count the number of nodes by using a hash table to keep track of the total number of distinct left or right borders.

Then we can use the Euler characteristic formula to compute the number of faces of a drawing of the graph:

V - E + F - C = 1

F = E - V + C + 1

To compute C, the number of connected components, we can use a depth-first search.

Note: This problem idea is borrowed from a recent Croatian programming contest, but please don't cheat by looking at the solution outlines. :)

• Are some of those bonuses decoys? – user2357112 Mar 26 '14 at 23:02
• @user2357112 Don't assume it can't be done unless you can prove it ;) – Niklas B. Mar 26 '14 at 23:28
• Well, with inputs guaranteed to fit in a machine integer, we could use a radix sort and call it O(n). I hate assuming restricted input size, because strictly speaking, it means there are finitely many possible inputs. – user2357112 Mar 26 '14 at 23:46
• @user2357112 No, I said you cannot assume the integers to be bounded while assessing the asymptotics, so neither radix sort nor counting sort would be linear time and space. That they fit into a word is just to make arithmetics "real" O(1) and for practical reasons (bounded variable width in most languages) – Niklas B. Mar 26 '14 at 23:47
• @NiklasB. if I have an algorithm in which the only component with superlinear complexity is the sorting, to I have to implement merge sort if my language uses quick sort, in order to get the n log n bonus? Also, I do have new conceptually new solution. Should I post a new answer of replace the old one? (I'd prefer the former, in case my new solution isn't actually correct) – Martin Ender Mar 27 '14 at 12:09

# Mathematica, 125 122 - 150 = -28 chars

I don't know the complexity of the built-in function ConnectedComponents.

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&


Usage:

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]


11

• I think we can safely assume that ConnectedComponents has linear expected worst-case complexity, so if there are O(n) components, this would be fine. I don't understand Mathematica, so I can't tell whether it is O(n) overall and qualifies for the -150 bonus? I think it does. Do I just run it with input in STDIN? – Niklas B. Mar 29 '14 at 15:51
• @NiklasB. his input method is just passing a string variable to an anonymous function. so I think that should qualify. as for the output, in Mathematica this will simply result in the number ending up in console output, so that should probably be fine, too. – Martin Ender Mar 29 '14 at 15:57
• I've verified the correctness of this, so I think with a score of -28 this is the new leader. Congratulations! – Niklas B. Mar 29 '14 at 16:17
• @NiklasB. why only 150? Which part of the algorithm has superlinear worst-case complexity? – Martin Ender Mar 29 '14 at 17:17
• @m.buettner 150 is for O(n) expected time. For graphs with arbitrary numbers as nodes, implicitly defined like here, you just can't find the number of CCs in linear time, which can be shown by reducing element distinctness to connected components. I think we can also reduce element distinctness to the original problem – Niklas B. Mar 29 '14 at 17:32

## Ruby - 312306285273269 259 characters

This answer has been superseded by my other approach which uses considerably less characters and runs in O(n log n).

Okay, let's go. For starters, I just wanted a working implementation, so this is not algorithmically optimised yet. I sort the circles from largest to smallest, and build a tree (circles included in other circles are children of those larger ones). Both operations take O(n^2) at worst and O(n log n) at best. Then I iterate through the tree to count areas. If the children of a circle fill up its entire diameter, there are two new areas, otherwise there is just one. This iteration take O(n). So I have overall complexity O(n^2) and qualify for neither reward nor penalty.

This code expects the input without the number of circles to be stored in a variable s:

t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a


Ungolfed version (expects input in variable string):

list = []
string.split("\n").map { |x|
m = x.split
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
i = -1
node = tree
while c=node[i+=1]
if circle[:x]<c[:l]
break
elsif circle[:x]<c[:r]
node = c[:children]
i = -1
end
end
node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
d = 0
i = -1
while c=node[:children][i+=1]
count.call c
d += c[:d]
end
areas += d == node[:d] ? 2 : 1
})
p areas

• @NiklasB. yes that test case would be nice. The relation that defines the edges in my tree is simply inclusion of one circle in another. Since on circle can't be contained in two circles that don't contain each other (due to the "one intersection" condition), I don't see how this could be a DAG. – Martin Ender Mar 27 '14 at 0:00
• Are a node's grandchildren also its children? – user2357112 Mar 27 '14 at 0:05
• @user2357112 no, because they can only split their direct parent – Martin Ender Mar 27 '14 at 0:06
• @NiklasB. If I run it with the example in your question, I get 11. For the one in your comment 9. – Martin Ender Mar 27 '14 at 0:21
• @NiklasB. wait, I actually get 10 and 8 with my ungolfed version, but 11 and 9 with my current golfed version :D – Martin Ender Mar 27 '14 at 0:22

## Ruby, 203183173 133 - 100 = 33 characters

So here is a different approach. This time, I sort the circles by their left-most point. Circles touching at their left-most point are sorted from largest to smallest. This takes O(n log n) (well, Ruby uses quick sort, so actually O(n^2) but implementing merge/heap sort is probably beyond the scope of this challenge). Then I iterate over this list, remembering all left-most and right-most positions of the circles I have visited. This allows me to detect if a series of circles connects all the way across an enclosing larger circle. In this case, there are two subareas, otherwise just one. This iteration takes only O(n) giving a total complexity of O(n log n) which qualifies for the 100 character reward.

This snippet expects the input to be supplied via a file in the command-line arguments without the number of circles:

l,r={},{}
a=1
\$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a


Ungolfed version (expects input in a variable string):

list = []
string.split("\n").map { |x|
m = x.split
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
x,y=circle[:l],circle[:r]
if l[x] && r[y]
areas += 2
else
areas += 1
l[y]=1 if l[x]
end
r[y]=1
l[x]=1
}
p areas

• Unfortunately this fails for all the larger testcases. It is fast though ;) I don't have a small failing example this time, but you can find the test data on the contest website I linked to (it's contest #6) – Niklas B. Mar 27 '14 at 15:34
• The first failing testcase is kruznice/kruznice.in.2 which is the first "real" test case so I assume there is something fundamentally wrong woth the algorithm or implementation. Does it work correct with arbitrarily nested circles? – Niklas B. Mar 27 '14 at 15:38
• @NiklasB. thanks, I'll have a look into the test cases (might take me until tomorrow night to fix it though) – Martin Ender Mar 27 '14 at 15:41
• @NiklasB. I figured out the problem and the minimum failing example requires 5 circles: -1 1 1 1 0 2 4 2 0 6. I'll think about how to fix this by tomorrow night (hopefully). – Martin Ender Mar 27 '14 at 18:20
• Your complexity analysis seems to assume that associative array access is constant time. That seems unlikely to be true in the worst case. – Peter Taylor Mar 27 '14 at 18:29

## Julia - 260 -100(bonus?) = 160

Interpreting the circles as figures with vertices (intersections), edges, and faces (areas of the plane) we can relate each other using Euler characteristic, so we only need to know the number of "vertices" and "edges" to have the number of "faces" or regions of the plane with the formula written below:

UPDATE: By thinking a while i figured out that the problem with my method was only when circles where not connected, so i came with an idea, why not artificially connect them? So the whole will satisfy the Euler formula.

F = 2+E-V (V=6, E=9)

[Dont work with nested circles, so its not an answer of the problem for general cases]

Code:

s=readlines(open("s"))
n=int(s[1])
c=zeros(n,2)
t=[]
for i=1:n
a=int(split(s[i+1]))
c[i,1]=a[1]-a[2]
c[i,2]=a[1]+a[2]
if i==1 t=[c[1]]end
append!(t,[c[i,1]:.5:c[i,2]])
end
e=0
t=sort(t)
for i in 1:(length(t)-1) e+=t[i+1]-t[i]>=1?1:0end #adds one edge for every gap
2+2n+e-length(unique(c)) # 2+E-V = 2+(2n+e)-#vertices

• I think your program will fail for 2 -10 1 10 1. – Niklas B. Mar 27 '14 at 0:39
• "It is guaranteed that no pair of circles has more than one common point." so i think it will not apply :) – CCP Mar 27 '14 at 0:44
• @CCP They have zero common points. n=2, the circles are (C=(-10,0), r=1) and (C=(10,0), r=1) – Niklas B. Mar 27 '14 at 0:44
• Doesn't the graph have to be connected to apply the Euler characteristic? – user2357112 Mar 27 '14 at 1:13
• Ah, here is a simple case: 4 0 2 1 1 10 2 11 1 But I don't think I can give you a lot more test cases, that would be a bit unfair – Niklas B. Mar 27 '14 at 2:22

## Spidermonkey JS, 308, 287, 273 - 100 = 173

I think if I rewrote this in Ruby or Python I could save characters.

Code:

for(a=[d=readline],e={},u=d(n=1);u--;)[r,q]=d().split(' '),l=r-q,r-=-q,e[l]=e[l]||[0,0],e[r]=e[r]||[0,0],e[r][1]++,e[l][0]++
for(k=Object.keys(e).sort(function(a,b)b-a);i=k.pop();a.length&&a.pop()&a.push(0)){for([l,r]=e[i];r--;)n+=a.pop()
for(n+=l;l--;)a.push(l>0)}print(n)


Algorithm:

n = 1 // this will be the total
e = {x:[numLeftBounds,numRightBounds]} // imagine this as the x axis with a count of zero-crossings
a = [] // this is the stack of circles around the "cursor".
// values will be 1 if that circle's never had alone time, else 0
k = sort keys of e on x
for each key in k: // this is the "cursor"
n += key[numLeftBounds] // each circle that opens has at least one space.
k[numRightBounds].times {n += a.pop()} // pop the closing circles. if any were never alone, add 1
k[numLeftBounds].times {a.push(alwaysAlone)} // push the opening circles
if !a.empty():
set the innermost circle (top of stack) to false (not never alone)
fi
loop


I'm not terribly great at big O notation, but I think that's O(n) since I'm effectively looping through each circle 3 times (create, left, right) and also sorting the map's keys (and I sort for O(n log n) but that disappears). Is this deterministic?

• If anyone has any advice on how to combine the r loop and the l loop into one statement, i'd appreciate it. – Not that Charles Mar 28 '14 at 12:55
• Cheers :) Looks to me like your runtime is indeed O(n log n), due to the sort, which would be -100. I will let you know whether it passes all test cases. – Niklas B. Mar 28 '14 at 14:00
• Nice, your program passes all test cases on the first try. I think something like this (sweepline with some state maintained in a stack) was the official solution from the problem authors. Your program gets a total score of 173 – Niklas B. Mar 28 '14 at 14:56
• @NiklasB. Thanks! – Not that Charles Mar 28 '14 at 18:03
• I was trying a much more robust solution with overlapping circles.... then I saw that they could only intersect at one point. – Not that Charles Mar 28 '14 at 18:48

# JavaScript (ES6) - 255 254 Characters - 100 250 Bonus = 155 4

R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1


Assumes that the input string is in the variable S and outputs the number of regions to the console.

R=/(\S+) (\S+)/ym;                  // Regular expression to find centre and width.
N=1;                                // Number of regions
w=l=0;                              // Maximum width and minimum left boundary.
X=[];                               // A 1-indexed array to contain the circles.
// All the above are O(1)
for(;m=R.exec(S);){                 // For each circle
X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};
// Create an object with w (width), l (left boundary)
// and r (right boundary) attributes.
l=k<l?k:l;                      // Update the minimum left boundary.
w=j<w?w:j                       // Update the maximum width.
}                                   // O(1) per iteration = O(N) total.
M=[];                               // An array.
X.map(x=>M[(x.l-l+1)*w-x.w]=x);     // Map the 1-indexed array of circles (X) to a
// sparse array indexed so that the elements are
// sorted by ascending left boundary then descending
// width.
// If there are N circles then only N elements are
// created in the array and it can be treated as if it
// is a hashmap (associative array) with a built in
// ordering and as per the rules set in the question
// is O(1) per insert so is O(N) total cost.
// Since the array is sparse then it is still O(N)
// total memory.
s=[];                               // An empty stack
i=0;                                // The number of circles on the stack.
M.map(x=>{                          // Loop through each circle
while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
// of the circles on the stack;
N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
// circle that pops off has radius equal to the total
// radii of its children then increment the number of
// regions by 1.

// Since there can be at most N items on the stack then
// there can be at most N items popped off the stack
// over all the iterations; therefore this operation
// has an O(N) total cost.
i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
// is its child. Decrement the parent's radius by the
// O(1) per iteration
s[i++]=x                        // Add the current circle to the stack.
});
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
// stack and if the circle that pops off has radius
// equal to the total radii of its children then
// increment the number of regions by 1.
// Since there will always be at least one circle on the
// stack then this has the added bonus of being the final
// command so the value of N is printed to the console.
// As per the previous comment on the complexity, there
// can be at most N items on the stack so between this
// and the iterations over the circles then there can only
// be N items popped off the stack so the complexity of
// all these tests on the circles on the stack is O(N).


The time complexity is now O(N).

Test Case 1

S='2\n1 3\n5 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1


Outputs: 3

Test Case 2

S='3\n2 2\n1 1\n3 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1


Outputs: 5

Test Case 3

S='4\n7 5\n-9 11\n11 9\n0 20';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1


Outputs: 6

Test Case 4

S='9\n38 14\n-60 40\n73 19\n0 100\n98 2\n-15 5\n39 15\n-38 62\n94 2';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1


Outputs: 11

Test Case 5

S='87\n-730 4\n-836 2\n-889 1\n-913 15\n-883 5\n-908 8\n-507 77\n-922 2\n-786 2\n-782 2\n-762 22\n-776 2\n-781 3\n-913 3\n-830 2\n-756 4\n-970 30\n-755 5\n-494 506\n-854 4\n15 3\n-914 2\n-840 2\n-833 1\n-505 75\n-888 10\n-856 2\n-503 73\n-745 3\n-903 25\n-897 1\n-896 2\n-848 10\n-878 50\n-864 2\n0 1000\n-934 6\n-792 4\n-271 153\n-917 1\n-891 3\n-833 107\n-847 3\n-758 2\n-754 2\n-892 2\n-738 2\n-876 2\n-52 64\n-882 2\n-270 154\n-763 3\n-868 72\n-846 4\n-427 3\n-771 3\n-767 17\n-852 2\n-765 1\n-772 6\n-831 1\n-582 2\n-910 6\n-772 12\n-764 2\n-907 9\n-909 7\n-578 2\n-872 2\n-848 2\n-528 412\n-731 3\n-879 1\n-862 4\n-909 1\n16 4\n-779 1\n-654 68\n510 490\n-921 3\n-773 5\n-653 69\n-926 2\n-737 3\n-919 1\n-841 1\n-863 3';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1


Outputs: 105

Previous Version

C=S.split('\n');N=1+C.shift()*1;s=[];C.map(x=>x.split(' ')).map(x=>[w=x[1]*1,x[i=0]*1+w]).sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d).map(x=>{while(i&&s[i-1][1]<x[1])N+=s[--i][0]?0:1;i&&(s[i-1][0]-=x[0]);s[i++]=x});while(i)N+=s[--i][0]?0:1


C=S.split('\n');                    // Split the input into an array on the newlines.
// O(N)
N=1+C.shift()*1;                    // Remove the head of the array and store the value as
// if there are N disjoint circles then there will be
// N+1 regions.
// At worst O(N) depending on how .shift() works.
s=[];                               // Initialise an empty stack.
// O(1)
C .map(x=>x.split(' '))             // Split each line into an array of the two values.
// O(1) per line = O(N) total.
.map(x=>[w=x[1]*1,x[i=0]*1+w])    // Re-map the split values to an array storing the
// radius and the right boundary.
// O(1) per line = O(N) total.

.sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d)
// Sort the circles on increasing left boundary and
// O(1) per comparison = O(N.log(N)) total.
.map(x=>{                         // Loop through each circle
while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
// of the circles on the stack;
N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
// circle that pops off has radius equal to the total
// radii of its children then increment the number of
// regions by 1.

// Since there can be at most N items on the stack then
// there can be at most N items popped off the stack
// over all the iterations; therefore this operation
// has an O(N) total cost.
i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
// is its child. Decrement the parent's radius by the
// O(1) per iteration
s[i++]=x                        // Add the current circle to the stack.
});
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
// stack and if the circle that pops off has radius
// equal to the total radii of its children then
// increment the number of regions by 1.
// Since there will always be at least one circle on the
// stack then this has the added bonus of being the final
// command so the value of N is printed to the console.
// As per the previous comment on the complexity, there
// can be at most N items on the stack so between this
// and the iterations over the circles then there can only
// be N items popped off the stack so the complexity of
// all these tests on the circles on the stack is O(N).


The total time complexity is O(N) for everything except the sort which is O(N.log(N)) - however replacing this with a bucket sort, this will reduce the total complexity to O(N).

The memory required is O(N).

Guess what is next on my todo list... bucket sort in less than 150 characters. Done

• Bucket sort has only average complexity O(n) (in fact O(n+k)), but O(n^2) or O(n log n) worst case depending on the sorting algorithm used within buckets, so you'd need to do it in 50 characters. – Martin Ender Mar 29 '14 at 10:32
• @m.buettner - Bucket sort can be done in O(N) worst-case complexity. It relies on careful choice of the buckets and an O(1) algorithm to assign to buckets. I've done it before (and proved it) and I just need to transfer the code to JavaScript. The algorithm above is already O(N.log(N)) so the only improvement is to get an O(N) sorting algorithm. – MT0 Mar 29 '14 at 10:43
• I'd be interested in that proof and corresponding choice of buckets. :) – Martin Ender Mar 29 '14 at 10:44
• cs.princeton.edu/~dpd/Papers/SCG-09-invited/… (on page 556) gives an example of an O(N) bucket sort. archive.org/stream/PlanarityTestingByPathAddition/… (page 75) gives an example of a O(N) combined DFS search and bucket sort (time complexity is discussed on page 76). – MT0 Mar 29 '14 at 14:55
• @Mt0 hold on there, you might to read my addition to the complexity section of the question. With unbounded numbers sorting in linear time is most definitely impossible – Niklas B. Mar 29 '14 at 15:18