GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #932 - Beautiful Array - LeetCode JavaScript Solutions

Back to all solutions

#932 - Beautiful Array

Medium • View on LeetCode • View on GitHub

Array Math Divide and Conquer

Problem Description

An array nums of length n is beautiful if:

nums is a permutation of the integers in the range [1, n].
For every 0 <= i < j < n, there is no index k with i < k < j where

2 * nums[k] == nums[i] + nums[j].

Given the integer n, return any beautiful array nums of length n.

There will be at least one valid answer for the given n.

Solution

/**
 * @param {number} n
 * @return {number[]}
 */
var beautifulArray = function(n) {
  const memo = new Map();
  return helper(n);

  function helper(size) {
    if (memo.has(size)) return memo.get(size);
    if (size === 1) return [1];

    const odds = helper(Math.ceil(size / 2));
    const evens = helper(Math.floor(size / 2));
    const result = [
      ...odds.map(x => x * 2 - 1),
      ...evens.map(x => x * 2)
    ];

    memo.set(size, result);
    return result;
  }
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.