No less code but easier to understand


  • 0
    C
        public int changeDirection(int row, int col, int direction, int[] edges) {
    		//edges{rightEdge,leftEdge,downEdge,upEdge};
    		if (direction == 0) {
    			if (col < edges[0])
    				return direction;
    			if (col == edges[0] && row < edges[2]) {
    				// right direction to down
    				edges[3]++;
    				return 1;
    			}
    		} else if (direction == 1) {
    			if (row < edges[2])
    				return direction;
    			if (row == edges[2] && col > edges[1]) {
    				// down direction to left
    				edges[0]--;
    				return 2;
    			}
    		} else if (direction == 2) {
    			if (col > edges[1])
    				return direction;
    			if (col == edges[1] && row > edges[3]) {
    				// left direction to up
    				edges[2]--;
    				return 3;
    			}
    		} else if (direction == 3) {
    			if (row > edges[3])
    				return direction;
    			if (row == edges[3] && col < edges[0]) {
    				// up direction to right
    				edges[1]++;
    				return 0;
    			}
    		}
    		return -1;
    	}
    	// position[0] --- row
    	// position[1] --- col
    	public int[] move(int [] position, int direction) {
    		switch (direction) {
    		case 0:
    			position[1]++;
    			break;
    		case 1:
    			position[0]++;
    			break;
    		case 2:
    			position[1]--;
    			break;
    		case 3:
    			position[0]--;
    			break;
    		}
    		return position;
    	}
            // Matrix I
    	public List<Integer> spiralOrder(int[][] matrix) {
    		List<Integer> spiral = new ArrayList<Integer>();
    		if (matrix == null)
    			return null;
    		if ( matrix.length == 0 || matrix[0].length == 0)
    			return spiral;
    		
    		// rightEdge,leftEdge,downEdge,upEdge;
    		int[] edges = { matrix[0].length - 1, 0, matrix.length - 1, 0 };
    		int[] position = {0,-1};
    		int direction = 0;
    		
    		while ((direction = changeDirection(position[0], position[1], direction, edges)) != -1) {
    			move(position, direction);
    			spiral.add(matrix[position[0]][position[1]]);
    		}
    		return spiral;
    	}
    // Matrix II
     public int[][] generateMatrix(int n) {
        int [][] matrix = {};
        if(n==0) return matrix;
        
        matrix = new int[n][n];
        int[] edges = { n - 1, 0, n - 1, 0 };
    	int[] position = {0,-1};
    	int direction = 0;
    	int i = 0;
    	while ((direction = changeDirection(position[0], position[1], direction, edges)) != -1) {
    		move(position, direction);
    		i++;
    		matrix[position[0]][position[1]] = i;
    	}
    	return matrix;
    }

  • 0
    T

    Magic constants galore! :) But I like:

    • that you didn't call indices i and j
    • that while loop
    • how position[x] are passed to changeDirection to show intention of no-modification

    Try this for easier understanding:

    private int maybeTurn(int row, int col, int dir, int[] edges) {
    	// if (dir) {
    	//     if (can step in dir) keep going;
    	//     if (reached end) {
    	//         forget what's left behind;
    	//         turn right;
    	//     }
    	// }
        if (dir == GO_RIGHT) {
            if (col < edges[RIGHT]) return dir;
            if (col == edges[RIGHT] && row < edges[BOTTOM]) {
                edges[TOP]++;
                return GO_DOWN;
            }
        } else if (dir == GO_DOWN) {
            if (row < edges[BOTTOM]) return dir;
            if (row == edges[BOTTOM] && col > edges[LEFT]) {
                edges[RIGHT]--;
                return GO_LEFT;
            }
        } else if (dir == GO_LEFT) {
            if (col > edges[LEFT]) return dir;
            if (col == edges[LEFT] && row > edges[TOP]) {
                edges[BOTTOM]--;
                return GO_UP;
            }
        } else if (dir == GO_UP) {
            if (row > edges[TOP]) return dir;
            if (row == edges[TOP] && col < edges[RIGHT]) {
                edges[LEFT]++;
                return GO_RIGHT;
            }
        }
        return STOP;
    }
    
    private void move(int [] pos, int dir) {
        switch (dir) {
            case GO_RIGHT:
                pos[COLUMN]++;
                break;
            case GO_DOWN:
                pos[ROW]++;
                break;
            case GO_LEFT:
                pos[COLUMN]--;
                break;
            case GO_UP:
                pos[ROW]--;
                break;
        }
    }
    
    // Matrix I
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null) return null;
        if (matrix.length == EMPTY || matrix[ROW].length == EMPTY) return Collections.emptyList();
    
        List<Integer> spiral = new ArrayList<Integer>(matrix.length * matrix[ROW].length);
        int[] edges = new int[4];
        edges[TOP] = edges[LEFT] = 0;
        edges[BOTTOM] = matrix.length - 1;
        edges[RIGHT] = matrix[ROW].length - 1;
        int[] pos = new int[2];
        pos[ROW] = 0;
        pos[COLUMN] = JUST_BEFORE;
        int dir = GO_RIGHT;
    
        while ((dir = maybeTurn(pos[ROW], pos[COLUMN], dir, edges)) != STOP) {
            move(pos, dir);
            spiral.add(matrix[pos[ROW]][pos[COLUMN]]);
        }
        return spiral;
    }
    
    // Matrix II
    public int[][] generateMatrix(int n) {
        if (n == EMPTY) return new int[EMPTY][EMPTY];
    
        int[][] matrix = new int[n][n];
        int[] edges = new int[4];
        edges[TOP] = edges[LEFT] = 0;
        edges[BOTTOM] = edges[RIGHT] = n - 1;
        int[] pos = new int[2];
        pos[ROW] = 0;
        pos[COLUMN] = JUST_BEFORE;
        int dir = GO_RIGHT;
    
        int i = 0;
        while ((dir = maybeTurn(pos[ROW], pos[COLUMN], dir, edges)) != STOP) {
            move(pos, dir);
            matrix[pos[ROW]][pos[COLUMN]] = ++i;
        }
        return matrix;
    }
    
    private static final int ROW = 0;
    private static final int COLUMN = 1;
    private static final int EMPTY = 0;
    private static final int JUST_BEFORE = -1;
    
    private static final int RIGHT = 0;
    private static final int LEFT = 1;
    private static final int BOTTOM = 2;
    private static final int TOP = 3;
    
    private static final int STOP = -1;
    private static final int GO_RIGHT = 0;
    private static final int GO_DOWN = 1;
    private static final int GO_LEFT = 2;
    private static final int GO_UP = 3;
    

    Notice how:

    • move's return value was not used
    • comments became redundant as
      if (dir == GO_RIGHT) ... return GO_DOWN; clearly indicates // right direction to down
    • it's possible to just reorder the constant values and the code doesn't break
      (except for matrix[ROW].length)
    • I may have overstepped a little with JUST_BEFORE, EMPTY and matrix[ROW].length

  • 0

    What do you have against i and j? They're the standard in both comp-sci and math.


  • 0
    T

    If I say int[] stuff = matrix[i], does stuff represent a row or a column?
    Compare with int[] stuff = matrix[row].

    That is using i/j leaves the ambiguity of row-first and column-first approaches.
    I know most matrix operations don't care (e.g. transpose), but I think it's better to pick one.

    The same goes for m and n for sizes. At least x and y on a grid have a suggestion of using a cartesian-like view (y is flipped).

    See for example https://leetcode.com/discuss/65653/an-iterative-python-solution-using-36ms


  • 0
    T

    Another argument is when writing a sorting algorithm, if you call the pivot j in QuickSort or maxIndex j in SelectionSort you lose meaning and it takes longer to decipher. This is most relevant when learning these algorithms, compare SelectionSort wiki code with InsertionSort wiki code: which one would you learn faster if you've never heard about them and you can only look at the code?


  • 0

    m and n are also the standard. m is height, n is width, i is the row index, j is the column index, and the row index comes first. I challenge you to find a single math book/site involving matrices that doesn't use m, n, i and j exactly like that.

    You'll even find exactly those letters used exactly like that in Chinese, in Arabic and in Russian, even though those languages have completely different characters in general.


  • 0

    If I say int[] stuff = matrix[i], does stuff represent a row or a column?

    The real problem here is that you called your variable "stuff". Should be int[] row = matrix[i].

    Using row for the row index is not just non-standard, it's also confusing. Because it isn't a row but only a row index.


  • 0
    T

    Continuing my other answer, introducing a little OO

    private static final int ROW = 0;
    private static final int EMPTY = 0;
    
    // Matrix I
    public List<Integer> spiralOrder(int[][] matrix) {
    	if (matrix == null) return null;
    	if (matrix.length == EMPTY || matrix[ROW].length == EMPTY) return Collections.emptyList();
    
    	List<Integer> spiral = new ArrayList<>(matrix.length * matrix[ROW].length);
    	Edges edges = new Edges(matrix.length, matrix[ROW].length);
    	Pos pos = new Pos();
    	Dir dir = Dir.GO_RIGHT;
    
    	while ((dir = dir.maybeTurn(pos.row, pos.col, edges)) != Dir.STOP) {
    		dir.move(pos);
    		spiral.add(pos.getFrom(matrix));
    	}
    	return spiral;
    }
    
    // Matrix II
    public int[][] generateMatrix(int n) {
    	if (n == EMPTY) return new int[EMPTY][EMPTY];
    
    	int[][] matrix = new int[n][n];
    	Edges edges = new Edges(n, n);
    	Pos pos = new Pos();
    	Dir dir = Dir.GO_RIGHT;
    
    	int i = 0;
    	while ((dir = dir.maybeTurn(pos.row, pos.col, edges)) != Dir.STOP) {
    		dir.move(pos);
    		pos.setInto(matrix, ++i);
    	}
    	return matrix;
    }
    
    private static class Pos {
    	int row = 0;
    	int col = -1;
    	int getFrom(int[][] matrix) { return matrix[row][col]; }
    	void setInto(int[][] matrix, int val) {matrix[row][col] = val; }
    }
    private static class Edges {
    	int left, right;
    	int top, bottom;
    	Edges(int rows, int cols) {
    		bottom = rows - 1;
    		right = cols - 1;
    	}
    }
    private enum Dir {
    	GO_LEFT {
    		@Override void move(Pos pos) { --pos.col; }
    		@Override Dir maybeTurn(int row, int col, Edges edges) {
    			if (col > edges.left) return this;
    			if (row == edges.top) return STOP;
    			edges.bottom--;
    			return GO_UP;
    		}
    	},
    	GO_RIGHT {
    		@Override void move(Pos pos) { ++pos.col; }
    		@Override Dir maybeTurn(int row, int col, Edges edges) {
    			if (col < edges.right) return this;
    			if (row == edges.bottom) return STOP;
    			edges.top++;
    			return GO_DOWN;
    		}
    	},
    	GO_UP {
    		@Override void move(Pos pos) { --pos.row; }
    		@Override Dir maybeTurn(int row, int col, Edges edges) {
    			if (row > edges.top) return this;
    			if (col == edges.right) return STOP;
    			edges.left++;
    			return GO_RIGHT;
    		}
    	},
    	GO_DOWN {
    		@Override void move(Pos pos) { ++pos.row; }
    		@Override Dir maybeTurn(int row, int col, Edges edges) {
    			if (row < edges.bottom) return this;
    			if (col == edges.left) return STOP;
    			edges.right--;
    			return GO_LEFT;
    		}
    	};
    	static Dir STOP = null;
    	abstract void move(Pos pos);
    	abstract Dir maybeTurn(int row, int col, Edges edges)/*{
    	    if (can step in dir) keep going;
    	    if (hits the wall if turned right) stop;
            forget what's left behind;
            turn right;
    	}*/;
    }

  • 0
    T

    I named it badly for effect, usually codes that use i/j/ii/jj, and the like don't name other variables in a meaningful way either.

    i is the row index, j is the column index
    I challenge you to find a single math book/site involving matrices that doesn't use m, n, i and j exactly like that.

    I actually started using meaningful names when I got fed up people not following that "standard" you mention, it was at university. Maybe it was a badly written/translated Hungarian books or the prof/lecturer's non-caring attitude when it came to examples, I'm not sure. See the two sorting algorithms wiki pages I linked for counter-examples.

    I give you that i/j is the tradition, but it doesn't mean it's a good one (watch this to fully understand where I'm coming from). I guess it was "invented" when they had no space to write longer variable names, or because they had no IDE support. I accept and use them when it's totally clear what's going on, that is: two simple nested for loops going in the same direction starting from roughly the same value. Or when I lack the understanding of the algorithm to give them meaningful names (x/y, r/c) :(

    To go back where it all started I gave him a compliment on the method signature, consider this:

    private int changeDirection(int row, int col, int direction, int[] edges);
    

    versus this (JavaDoc is usually omitted):

    /**
     * @param i the row index in the matrix
     * @param j the column index in the matrix
     */
    private int changeDirection(int i, int j, int direction, int[] edges);
    

    Note that all this is my personal view and I use it when I code for myself. I always adapt to the code style whenever I contribute, based on existing code or team standards.


  • 0
    T
    This post is deleted!

Log in to reply
 

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