Dart implementation, O(N^2)
Intuition\nIf we sort the array, the very first(i.e. min) element will belong to the low array, while one of the i-th elements belongs to the high array.\nSo we
# Intuition\nIf we sort the array, the very first(i.e. min) element will belong to the low array, while one of the i-th elements belongs to the high array.\nSo we can iterate trough difference b/w first and i-th element and check our array for the match.\n\n# Approach\nUse containers (splay tree map and hash map) to efficiently find pair element within O(N^2)\n\n# Complexity\n- Time complexity:\nO(N^2)\n\n- Space complexity:\nO(N)\n\n# Code\n```\n\nimport \'dart:collection\';\n\nclass Solution {\n  List<int> recoverArray(List<int> nums) {\n    final nm = SplayTreeMap<int, int>();\n    nums.forEach((n) { // n * log(n)\n      if (!nm.containsKey(n))\n        nm[n] = 1;\n      else\n        nm[n] = nm[n]! + 1;\n    });\n\n    int low = nm.firstKey()!;\n    for (int high in nm.keys) // N\n    {\n      int k = high - low;\n      if (k == 0 || k % 2 != 0) continue;\n      final check = Map<int, int>.fromEntries(nm.entries);\n      bool passed = true;\n      for (var v in nm.keys) { // * N\n        if (check[v] == 0) continue;\n        if (!check.containsKey(v + k) || check[v + k]! < check[v]!) {\n          passed = false;\n          break;\n        }\n        check[v + k] = check[v + k]! - check[v]!;\n      }\n      if (passed) {\n        return check.entries\n            .where((e) => e.value != 0)\n            .map((e) => List.generate(e.value, (index) => e.key + k ~/ 2))\n            .expand((element) => element)\n            .toList();\n      }\n    }\n    return [];\n  }\n}\n```
['Dart']