Array Reconstruction: Rebuild Original Array from Difference or Prefix-Sum Encoding

Problem You are given an encoded array diff of length n-1 where diff[i] = original[i+1] - original[i]. You are also given original[0]. Reconstruct and return the full original array. Example: Round 2 - Follow-up Variant Now you are given the array in shuffled order and the difference array in shuffled order, but you are NOT given original[0]. Determine if a valid reconstruction exists. If yes, return one valid original array. Follow-ups What is the time and space complexity of your reconstructio…