## Ordered Cartesian Coordinates

### April 21, 2015

Today’s exercise is a simple little interview question:

Generate the pairs of cartesian coordinates within a square bounded by (1,1) and (n,n) ordered by their product in ascending order. For instance, when n is 3, the coordinates are (1,1), (1,2), (2,1), (1,3), (3,1), (2,2), (2,3), (3,2) and (3,3). Can you find a solution with time complexity better than O(n2)?

Your task is to write a program to solve the interview question. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 16 Responses to “Ordered Cartesian Coordinates”

1. Rutger said

No, we cannot find a solution better than O(n^2).
This is because the result contains n^2 coordinates and we can produces each coordinate in O(1).

But using a Python generator we can produce them on demand, minimizing memory to O(1).

```

def coordinates(n):
for i in range(n):
for j in range(n):
yield (i,j)

for c in coordinates(3):
print c
```
2. Rutger said

Mm forgot the sorting constraint. In this case we need the entire list in memory anyways.. Sorting is O(n log n) << O(n^2).

def coordinates(n):
for i in range(n):
for j in range(n):
yield (i+1,j+1)

l = sorted( [c for c in coordinates(3)], key=lambda x: x*x )
print l

3. Jaime said

Sorting is actually O(n^2 log n^2), which is worse than O(n^2).

4. Rutger said

Mm true. What about the solution built by mr. Programming Praxis?
He uses a sort function (https://programmingpraxis.com/contents/standard-prelude/#sorting) as well (O(n log n), with n=#coordinates)

5. programmingpraxis said

I didn’t do it, but instead of a comparison-based sort at O(n log n) you could do a radix sort or some other O(n) sort. That would truly reduce the overall time to O(n2).

6. Jussi Piitulainen said

This Python, I believe, generates the sequence in O(n) space. There are n generator objects, one for each row of the multiplication table, which the heapq.merge combines to yield each (rk, (r, k)) in increasing order. The sequence is then pulled to memory at once for printing. That’s not merge’s fault.

```from heapq import merge
def row(r, n): return ((r * k, (r, k)) for k in	range(1, n + 1))
n = 3
print([p for w, p in merge(*(row(r, n) for r in range(1, n + 1)))])
```
7. Will_Ness said

The enumeration in descending order:

```enuNM n = foldi (\(x:xs) ys-> x : merge xs ys) [] \$
[ (x*x,(x,x)) :
concat [ [(z,(x,y)),(z,(y,x))]       -- two symmetrical pairs,
| y<- [x-1,x-2..1]  --  below and above the diagonal
, let z=x*y  ] | x<-[n,n-1..1]]

merge a@(x:xs) b@(y:ys) = if (fst y) > (fst x)
then  y : merge  a ys
else  x : merge  xs b
merge a [] = a
merge [] b = b

foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))

pairs f (x:y:t)  = f x y : pairs f t
pairs f t        = t
```

Reversing the sequence involves some straightforward changes in the code.

8. Will_Ness said

Forgot to add, the code’s in Haskell; it runs empirically at ~ n^1.08 producing first n=100,000 entries for a similar, slightly different problem (seen here ) at ranges on the order of 10^8.

9. Destabilizer said

I wrote this solution (on Python):
``` def coords(n): for i in range(n*n): yield(i//n+1, i%n+1) ```
So, I think it works for O(n).
In action:
``` >>> list(coords(4)) [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)] ```

10. Destabilizer said

11. Jussi Piitulainen said

@Destabilizer, the task was to yield the pairs “ordered by their product”, so (2, 1), for example, should come before (1, 3). It may or may not come before (1, 2), which has the same product. You’ve produced a “row-major” order, or it might be called a “lexicographic order”. (Nice expression of it, though.)

It’s also not O(n) time. Your yield statement is executed n² times which is more than O(n). Do see Praxis’s discussion or first comment above.

12. Rajeev. P said

class Program
{
static void Main(string[] args)
{
int n = 4;
Hashtable ht = new Hashtable();
int count =0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j 1)
{
if (!ht.ContainsValue(string.Format(“({0},{1})”, j, i)))
{
count++;
}
}
}
}
}

foreach (int key in ht.Keys.Cast().OrderBy(x=>x))
{
Console.WriteLine(ht[key]);
}

}
}

13. Rajeev. P said

Sorry HTML Truncated

class Program
{
static void Main(string[] args)
{
int n = 4;
Hashtable ht = new Hashtable();
int count =0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (!ht.ContainsValue(string.Format("({0},{1})", i, j)))
{
count++;
if (j > 1)
{
if (!ht.ContainsValue(string.Format("({0},{1})", j, i)))
{
count++;
}
}
}
}
}

foreach (int key in ht.Keys.Cast<int>().OrderBy(x=>x))
{
Console.WriteLine(ht[key]);
}

}
}

14. fisherro said

My first attempt, which I believe is correct.

```#include <vector>
#include <utility>
#include <iostream>

typedef std::vector<std::pair<int, int>> Coords;

void ugly_sort(Coords& v)
{
using namespace std::placeholders;
std::sort(v.begin(), v.end(),
std::bind(std::less<int>(),
std::bind(std::multiplies<int>(),
std::bind(&Coords::value_type::first, _1),
std::bind(&Coords::value_type::second, _1)),
std::bind(std::multiplies<int>(),
std::bind(&Coords::value_type::first, _2),
std::bind(&Coords::value_type::second, _2))));
}

void lambda_sort(Coords& v)
{
std::sort(v.begin(), v.end(),
[](const Coords::value_type& a, const Coords::value_type& b)
{ return (a.first * a.second) < (b.first * b.second); });
}

Coords generate(int n)
{
Coords v;
for (int x = 1; x <= n; ++x) {
for (int y = 1; y <= n; ++y) {
v.push_back(std::make_pair(x, y));
}
}
#if 0
ugly_sort(v);
#else
lambda_sort(v);
#endif
return v;
}

int main(int argc, char** argv)
{
auto v = generate(3);
for (const auto& p: v) {
std::cout << "(" << p.first << ", " << p.second << "): " <<
(p.first * p.second) << "\n";
}
}
```
15. fisherro said

I made a second attempt, but this one fails for n ≥ 5.

```#include <vector>
#include <utility>
#include <iostream>

//This one fails an n = 5.
std::vector<std::pair<int, int>> generate(int n)
{
std::vector<std::pair<int, int>> v;
for (int x = 1; x <= n; ++x) {
for (int y = x; y <= n; ++y) {
v.push_back(std::make_pair(x, y));
if (x != y) v.push_back(std::make_pair(y, x));
}
}
return v;
}

int main(int argc, char** argv)
{
auto v = generate(5);
for (const auto& p: v) {
std::cout << "(" << p.first << ", " << p.second << "): " <<
(p.first * p.second) << "\n";
}
}
```
16. cristi said

``` int i = 0;```
``` ```
``` for (i=1; i<N; i++) { printf("(%d,%d) ",i,i); printf("(%d,%d) ",i,i+1); printf("(%d,%d) ",i+1,i); if ( i+2 <= N ) { printf("(%d,%d) ",i,i+2); printf("(%d,%d)",i+2,i); } printf("\n"); } printf("(%d,%d)\n",N,N); ```