algoadvance

Leetcode 1502. Can Make Arithmetic Progression From Sequence

Problem Statement

Given an array of numbers arr, return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

An array is said to form an arithmetic progression if the difference between consecutive elements is the same.

Clarifying Questions

  1. Range and constraints of the input array:
    • What is the range of the length of the input array?
    • What is the range of the integers in the array?
  2. Properties of the input array:
    • Can the array contain negative numbers?
    • Can it contain duplicates?

Code

Let’s implement the function following these steps:

  1. If the array length is less than 2, return true.
  2. Sort the array.
  3. Compute the common difference between the first two elements.
  4. Iterate through the sorted array to check if each consecutive difference is the same.
  5. Return the result based on the iterations.
public class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        if (arr.length < 2) {
            return true;
        }
        
        Arrays.sort(arr);
        int commonDifference = arr[1] - arr[0];
        
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != commonDifference) {
                return false;
            }
        }
        
        return true;
    }
}

Strategy

  1. Sort the array: By sorting the array, we ensure that if it can form an arithmetic progression, the difference between consecutive elements should be constant.
  2. Compute the common difference: Calculate the difference between the first two elements since this difference should be constant for the entire sequence.
  3. Validation loop: Iterate through the remaining elements to check if the difference between consecutive elements matches the common difference computed.

Time Complexity

Thus, the overall time complexity of the solution is O(n log n) due to the sorting step.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI