Leetcode Random Challenge - Wk4 (48)

[Cicero]

Hi all,

New week, new challenge. Some pretty awesome submissions from last week.

This week another medium difficulty problem courtesy of the question picker, although I must admit I clicked it a few times because some are just weak:

48. Rotate Image - https://leetcode.com/problems/rotate-image/description/

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

How it works/Rules:

• We use the random question picker, and all attempt it, one question a week.
• No cheating/looking at the editorial solution until your soln is accepted on leetcode, and you're convinced you can't get it any quicker.
• Language is up to you, this may help people appreciate other languages as well
• Only post your time taken, language, and percentage of submissions beaten at first. Use spoiler tags for your code.

Good luck!

 

[[)roi(]]

Immutable Functional solution:

• Beats 95% of Swift submissions
• Time 13ms.

Spoiler

func rotate(_ matrix: inout [[Int]]) {
  if matrix.isEmpty { return }
  matrix = matrix[0].indices.map {i in matrix.reversed().map {$0[i]}}
}

In place mutation:

• Beats 95% of Swift submissions
• Time 11ms.

Spoiler

func rotate(_ matrix: inout [[Int]]) {
  if matrix.isEmpty { return }
  guard matrix.count == matrix[0].count else { return }
  
  func rotateBorder(offset: Int, size: Int) {
    let rangeLR = stride(from: size - offset, through: offset, by: -1)
    let rangeTB = stride(from: offset + 1, to: size - offset, by: 1)
    let left = rangeLR.map { matrix[$0][offset] }
    let right = rangeLR.map { matrix[$0][size - offset] }
    let top = rangeTB.map { matrix[offset][$0] }
    let bottom = rangeTB.map { matrix[size - offset][$0] }
    for i in left.indices {
      matrix[offset][i + offset] = left[i]
      matrix[size - offset][i + offset] = right[i]
    }
    for i in top.indices {
      matrix[offset + 1 + i][offset] = bottom[i]
      matrix[offset + 1 + i][size - offset] = top[i]
    }
  }
  
  let size = matrix.count
  for i in stride(from: 0, to: size / 2, by: 1) {
    rotateBorder(offset: i, size: size - 1)
  }
}

Alternative in-place mutation:

• Beats 100% of Swift submissions
• Time 6ms.

Spoiler

func rotate(_ matrix: inout [[Int]]) {
  if matrix.isEmpty { return }
  guard matrix.count == matrix[0].count else { return }
  for slice in 0 ..< matrix.count / 2 {
    let (first, last) = (slice, matrix.count - 1 - slice)
    for i in first ..< last {
      let (offset, top) = (i - first, matrix[first][i])
      matrix[first][i] = matrix[last - offset][first]
      matrix[last - offset][first] = matrix[last][last - offset]
      matrix[last][last - offset] = matrix[i][last]
      matrix[i][last] = top
    }
  }
}

Alternative in-place mutation that does something similar to the functional approach:

• Beats 100% of Swift submissions
• Time 5ms.

Spoiler

func rotate(_ matrix: inout [[Int]])
{
  if matrix.isEmpty { return }
  matrix.reverse()
  for row in 0 ..< matrix.count 
  {
    for col in (row + 1) ..< matrix[row].count 
    {
      (matrix[row][col], matrix[col][row]) = (matrix[col][row], matrix[row][col])
    }
  }
}

 

[Cicero]

First attempt:

• Beats 8.97% of submissions
• Time: 3ms

That percentage though, sigh :erm:

Although maybe there are just too few C submissions, or we all seem to be the same? I cannot select any quicker submission from the graph.

Spoiler

void rotate(int** matrix, int matrixRowSize, int matrixColSize) {
    int n,i,j,store, k; 
    n = matrixColSize-1;
    for (j=0; j<matrixColSize/2; j++) {          
        for (i=j; i<n; i++) {
            k = n-i+j;            
            store = matrix[j][i];
            matrix[j][i] = matrix[k][j];
            matrix[k][j] = matrix[n][k]; 
            matrix[n][k] = matrix[i][n];
            matrix[i][n] = store;
        }
        n--;
    }
}

 

[Cicero]

Immutable Functional solution:

• Beats 95% of Swift submissions
• Time 13ms.

Spoiler

func rotate(_ matrix: inout [[Int]]) {
  if matrix.isEmpty { return }
  matrix = matrix[0].indices.map {i in matrix.reversed().map {$0[i]}}
}

In place mutation:

• Beats 95% of Swift submissions
• Time 11ms.

Spoiler

func rotate(_ matrix: inout [[Int]]) {
  if matrix.isEmpty { return }
  guard matrix.count == matrix[0].count else { return }
  
  func rotateBorder(offset: Int, size: Int) {
    let rangeLR = stride(from: size - offset, through: offset, by: -1)
    let rangeTB = stride(from: offset + 1, to: size - offset, by: 1)
    let left = rangeLR.map { matrix[$0][offset] }
    let right = rangeLR.map { matrix[$0][size - offset] }
    let top = rangeTB.map { matrix[offset][$0] }
    let bottom = rangeTB.map { matrix[size - offset][$0] }
    for i in left.indices {
      matrix[offset][i + offset] = left[i]
      matrix[size - offset][i + offset] = right[i]
    }
    for i in top.indices {
      matrix[offset + 1 + i][offset] = bottom[i]
      matrix[offset + 1 + i][size - offset] = top[i]
    }
  }
  
  let size = matrix.count
  for i in stride(from: 0, to: size / 2, by: 1) {
    rotateBorder(offset: i, size: size - 1)
  }
}

Alternative in-place mutation:

• Beats 100% of Swift submissions
• Time 6ms.

Spoiler

func rotate(_ matrix: inout [[Int]]) {
  if matrix.isEmpty { return }
  guard matrix.count == matrix[0].count else { return }
  for slice in 0 ..< matrix.count / 2 {
    let (first, last) = (slice, matrix.count - 1 - slice)
    for i in first ..< last {
      let (offset, top) = (i - first, matrix[first][i])
      matrix[first][i] = matrix[last - offset][first]
      matrix[last - offset][first] = matrix[last][last - offset]
      matrix[last][last - offset] = matrix[i][last]
      matrix[i][last] = top
    }
  }
}

Man, your first one is insanely simple and concise, prefer it regardless of the time leetcode reports.

Alternative in-place solution is very similar to mine as well.

 

[[)roi(]]

some more c alternatives:

Spoiler

void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

void reverse(int **matrix, int matrixRowSize)
{
  for (int r = 0; r < matrixRowSize / 2; r++)
  {
    swaprow(&matrix[r], &matrix[matrixRowSize - r - 1]);
  }
}

void rotate(int **matrix, int matrixRowSize, int matrixColSize) {
  reverse(matrix, matrixRowSize);
  for (int r = 0; r < matrixRowSize; r++) {
    for (int c = (r + 1); c < matrixColSize; c++) {
      swap(&matrix[r][c], &matrix[c][r]);
    }
  }
}

Spoiler

void rot4(int *a, int *b, int *c, int *d)
{
  int temp = *a;
  *a = *b;
  *b = *c;
  *c = *d;
  *d = temp;
}

void rotate(int **matrix, int matrixRowSize, int matrixColSize) {
  int last = matrixRowSize - 1;
  for (int r = 0; r < matrixRowSize / 2; ++r) {
    for (int c = r; c < last - r; ++c) {
      rot4(&matrix[last - c][r],
            &matrix[last - r][last - c],
            &matrix[c][last - r],
            &matrix[r][c]);
    }
  }
}

As for the times; both times are 3ms and similarly match Cicero's grouping which is strange; appears the leet server algorithm rating is based solely on ms, which is highly flawed as it's affected by server load. running the same algorithms at different times reveals huge deviations in groupings & ms -- so i suspect that with increased server load, it has all but become impossible to rank top with certain older challenges simply because execution is affected by the increased load.

 

[Cicero]

some more c alternatives:

Spoiler

void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

void reverse(int **matrix, int matrixRowSize)
{
  for (int r = 0; r < matrixRowSize / 2; r++)
  {
    swaprow(&matrix[r], &matrix[matrixRowSize - r - 1]);
  }
}

void rotate(int **matrix, int matrixRowSize, int matrixColSize) {
  reverse(matrix, matrixRowSize);
  for (int r = 0; r < matrixRowSize; r++) {
    for (int c = (r + 1); c < matrixColSize; c++) {
      swap(&matrix[r][c], &matrix[c][r]);
    }
  }
}

Spoiler

void rot4(int *a, int *b, int *c, int *d)
{
  int temp = *a;
  *a = *b;
  *b = *c;
  *c = *d;
  *d = temp;
}

void rotate(int **matrix, int matrixRowSize, int matrixColSize) {
  int last = matrixRowSize - 1;
  for (int r = 0; r < matrixRowSize / 2; ++r) {
    for (int c = r; c < last - r; ++c) {
      rot4(&matrix[last - c][r],
            &matrix[last - r][last - c],
            &matrix[c][last - r],
            &matrix[r][c]);
    }
  }
}

As for the times; both times are 3ms and similarly match Cicero's grouping which is strange; appears the leet server algorithm rating is based solely on ms, which is highly flawed as it's affected by server load. running the same algorithms at different times reveals huge deviations in groupings & ms -- so i suspect that with increased server load, it has all but become impossible to rank top with certain older challenges simply because execution is affected by the increased load.

Yeah, the timings are a bit dodge. I guess they are useful for massive efficiency changes to your code, but pretty useless for measuring smaller changes.

But jeesh, where is everybody for this week? Just you and I roi?

 

[[)roi(]]

Yeah, the timings are a bit dodge. I guess they are useful for massive efficiency changes to your code, but pretty useless for measuring smaller changes.

But jeesh, where is everybody for this week? Just you and I roi?

Yeah, the timings are a bit dodge. I guess they are useful for massive efficiency changes to your code, but pretty useless for measuring smaller changes.

But jeesh, where is everybody for this week? Just you and I roi?

I tried a similar *crickets* thread last year, suspect most:

• are too busy
• prefer discussion only
• could be bothered
• bit shy to share code

Btw what languages do you code in?

 

[Cicero]

I tried a similar *crickets* thread last year, suspect most:

• are too busy
• prefer discussion only
• could be bothered
• bit shy to share code

Btw what languages do you code in?

True, and I can understand that, not everyone has the time/inclination. Although if you're in software dev this kind of practice would help in interviews at the end of the day. To avoid a Max Howell situation https://twitter.com/mxcl/status/608682016205344768?lang=en-gb

I'm an embedded C programmer, electronic engineering background. Which means my coding skills are pretty shoddy compared to a CS professional, in my opinion. We spend a lot of time on electronics and very low level stuff, and don't even touch algorithms, data structures and whatnot.

I write a lot of C, and then a bit of Python and Tcl, and touch a bit of web stuff every now and then - although I like to avoid that as much as I can.

I enjoy this kind of thing though because it pushes me to think slightly differently to what I do every day, and hopefully become a better general programmer.

What about you?

 

[[)roi(]]

True, and I can understand that, not everyone has the time/inclination. Although if you're in software dev this kind of practice would help in interviews at the end of the day. To avoid a Max Howell situation https://twitter.com/mxcl/status/608682016205344768?lang=en-gb

Max ended up working or Apple for a bit; i.e. proof that skilled resource can always find a decent alternative. Ultimately he decided he didn't like the corporate slugfest and resigned to resume his contract work.

I'm an embedded C programmer, electronic engineering background. Which means my coding skills are pretty shoddy compared to a CS professional, in my opinion. We spend a lot of time on electronics and very low level stuff, and don't even touch algorithms, data structures and whatnot.

I write a lot of C, and then a bit of Python and Tcl, and touch a bit of web stuff every now and then - although I like to avoid that as much as I can.

I enjoy this kind of thing though because it pushes me to think slightly differently to what I do every day, and hopefully become a better general programmer.

What about you?

I've been programming for a very long time; 35+ years; so I've done my penance almost all of the mainstream languages and many period / industry specific ones. Over the last decade my contract income has been primarily derived from work in C++, C#, Java, Kotlin, Objective-C, PHP, Ruby, and Swift.

Only reason I asked is that if this thread doesn't end up delivering what you hoped for; we could always try a different approach: pick a common language (or an unfamiliar one) + some interesting challenge, and jointly work on that on gitHub or bitbucket.

 

[animal531]

I'm a bit swamped at work these days, so I only get to drop a comment here and there :/
But I enjoy looking at all the entries everyone is coming up with.