CHFADJSUM - Editorial

editorial
, ,
1

Problem Link - Chef And Adjacent Sums Practice Coding Problem

Problem Statement:

Given an array A of size N, we need to determine whether we can rearrange the elements of A such that for all adjacent pairs in the rearranged array, their sum is strictly less than Z, where: Z = B[N] + B[N−1]. Here, B is the array A sorted in non-decreasing order.
For each test case, output “YES” if such a rearrangement exists, otherwise output “NO”.

Approach:

Observations:

  • Z is the sum of the two largest elements in the array.
  • To satisfy the condition (A[i]+A[i+1])<Z for all i, the rearrangement should avoid placing the two largest elements next to each other.
  • The frequency of the largest or second-largest elements must not dominate the array, as it would force them to be adjacent.

Special Cases:

  • If the largest element occurs too many times (more than half of N), it is impossible to avoid adjacency.

Plan:

  • Sort the array A to compute Z.
  • Check the frequency of the largest element. If it appears more than ⌈N/2⌉ times, output “NO”.
  • Otherwise, check the adjacency condition using frequency analysis of the largest and second-largest elements.

Complexity:

  • Time Complexity: Sorting takes O(N log ⁡N). Frequency Count takes O(N). Overall Complexity will come as O(N log ⁡N).
  • Space Complexity: * A map (or unordered_map) is used to store the frequency of elements. In the worst case, all elements are unique, so the map requires O(N) space for N key-value pairs.