Zigzag traversal of a two-dimensional array

user_13880394 0
Viewed 327

I need to traverse a two-dimensional array in a zigzag and pick the elements along the way:

From:

[['','','',''],
 ['','','',''],
 ['','','',''],
 ['','','','']]

To:

['','','','','','','','','','','','','','','','']

My approach was to use a for loop, check each index of the first array and compare it against the index of the next array and then if that number is bigger by one push it into the new one dimensional array.

What is the best approach to solve this? Do you have some resources to learn more about this pattern?

traversal javascript
3 Answers

UPDATED ANSWER

This function will merge arrays in zigZag way.

Here I have shown example with 2 arrays with different data type values.

function zigZag(array) {
    let arrayLength = array.length;
    let arrayItemLength = array[0].length;
    let result = [];
    let flag = true;

    for(let i = 0; i < (arrayLength + (arrayLength / 2) + 1) ; i++) {
        if(i < arrayItemLength) {
            let length = (i + 1);
            let ii = i;
            for(let j = 0; j < length; j++) {
                if(flag == true) result.push(array[j][ii]);
                else result.push(array[ii][j]);
                ii-=1;
            }
        }else {
            let ii = (i + 1) - arrayItemLength;

            for(let j = arrayItemLength - 1; j > i - arrayItemLength; j--) {
                if(flag == true) result.push(array[ii][j]);
                else result.push(array[j][ii]);
                ii+=1;
            }
        }
        if(flag == true) flag = false;
        else flag = true;
    }

    return result;
}

let array = [
    ["" , "" , "" , "" ],
    ["" , "" , "" , "" ],
    ["" , "" , "" , "" ],
    ["" , "" , "" , "" ],
];

let array_1 = [
    [1, 3, 4, 10],
    [2, 5, 9, 11],
    [6, 8, 12, 15],
    [7, 13, 14, 16],
];

console.log(zigZag(array)); // icons
console.log(zigZag(array_1)); // numbers

OLD ANSWER

Try this, I think this what you want to do.

let array = [
    [1, 3, 4, 10],
    [2, 5, 9, 11],
    [6, 8, 12, 15],
    [7, 13, 14, 16],
];

function mergeArray(array) {
    let merged = array.reduce((item, total) => [...total, ...item], []);
    return merged.sort((a, b) => a - b);
}

let result = mergeArray(array);

console.log(result)

user_161355110

OLD ANSWER:

you can use .flat() method for javascript array. Array.flat()

let array = [
    [1, 3, 4, 10],
    [2, 5, 9, 11],
    [6, 8, 12, 15],
    [7, 13, 14, 16],
]
const flatArray = array.flat()
flatArray.sort((a,b)=>a-b)
console.log(flatArray)

UPDATE ANSWER: after question update output 

const items = [
    [1, 3, 4, 10],
    [2, 5, 9, 11],
    [6, 8, 12, 15],
    [7, 13, 14, 16],
];

/*const items =  [
  [ ,  ,  ,  ],
  [ ,  ,  ,  ],
  [ ,  ,  ,  ],
  [ ,  ,  ,  ],
]*/

function zigZag(arr) {
    let array = []
    const itemCounts = arr.reduce((pre, cur)=> pre+cur.length,0)    
    for(let i=0; i<itemCounts; i+=1){
        let round = []
        for(let j=0; j<arr.length; j+=1){
            if(arr[j].length){
                round.push({
                    value: arr[j][0],
                    row:j
                })
            }
            
        }
        const minValue = Math.min(...round.map(item=>item.value))
        const target = round.find(item=>item.value == minValue)
        array.push(arr[target.row].shift())
    }    
    return array;
};

console.log(zigZag(items))

user_78657590

My understanding is that you want to transform a n×n array such as:

[ ['', '', '', '']

, ['', '', '', '']

, ['', '', '', '']

, ['', '', '', ''] ]

into:

['','','','','','','','','','','','','','','','']

Let's transform the original array into a "matrix of positions" and let's try to picture the "zigzag":

[ [[0,0], [0,1], [0,2], [0,3]]
// ↙      ↗      ↙      ↗
, [[1,0], [1,1], [1,2], [1,3]]
// ↗      ↙      ↗      ↙
, [[2,0], [2,1], [2,2], [2,3]]
// ↙      ↗      ↙      ↗
, [[3,0], [3,1], [3,2], [3,3]]
// ↗      ↙      ↗      ↙
]

If we focus on the edges we can start working out a pattern:

[ [0,0]
, [1,0], /* … */ [0,1]
, [2,0], /* … */ [0,2]
, [3,0], /* … */ [0,3]
, [3,1], /* … */ [1,3]
, [3,2], /* … */ [2,3]
,                [3,3] ]

Now we need to work out all the [x,y] between each edges and traverse each edge in opposite direction:

const inp1 = zigzag([ ['', '', '', '']

                    , ['', '', '', '']

                    , ['', '☝️', '', '']

                    , ['', '', '', ''] ]);

const inp2 = zigzag([ ['', '', '']

                    , ['', '', '']

                    , ['', '☝️', ''] ]);

const inp3 = zigzag([ ['', '']

                    , ['', ''] ]);

const inp4 = zigzag([ [''] ]);

console.log(`
  [${String(inp1)}]
  [${String(inp2)}]
  [${String(inp3)}]
  [${String(inp4)}]
`);
<script>
const zigzag = inp => {
  const m = inp.length - 1;
  const edges = [];
  for (let x = 0; x <= m; x++) edges.push([x, 0]);
  for (let x = 1; x <= m; x++) edges.push([m, x]);
  return edges.flatMap(([x, y], i) => {
    const path = [[x, y]];
    for (let a = x, b = y; a != y && b != x;) path.push([--a, ++b]);
    return (i % 2 ? path : path.reverse()).map(([x, y]) => inp[x][y]);
  });
}
</script>

user_12448840
Related