Array With Elements Not Equal to Average of Neighbors LeetCode solution in C++

1
// Approach-1 (Using sorting O(nlogn))
2
/*
3
    If you make sure that
4
    nums[i-1] < nums[i] > nums[i+1]
5
    You are good to go.
6

7
    So, just sort the input and choose wisely to satisfy above condition.
8

9
    Example :
10
    [6,2,0,9,7]
11
    sort it : [0, 2, 6, 7, 9]
12

13
    result : [0, _, 2, _, 6] - 1st loop (fill alternaltely)
14
    result : [0, 7, 2, 9, 6] - 2nd loop (fill next larger numbers from nums to
15
   result in spaces left)
16

17
*/
18

19
class Solution {
20
 public:
21
  vector<int> rearrangeArray(vector<int> &nums) {
22
    int n = nums.size();
23
    sort(begin(nums), end(nums));
24

25
    vector<int> result(n);
26
    int j = 0;
27
    int i = 0;
28
    for (; i < n && j < n; i++, j += 2) // alternately fill so that you leave
29
                                        // one space in between for large number
30
      result[j] = nums[i];
31

32
    j = 1;
33
    for (; i < n && j < n; i++,
34
                           j += 2) // filter the large number in spaces between that we left above
35
      result[j] = nums[i];
36

37
    return result;
38
  }
39
};