Find the biggest perfect square in an array

An algorithm to find the largest perfect square in an array. Return -1 if not found.

Example

Input:
[1 ,10 ,19 ,27 ,25 ,23]
[7, 33, 55, 26, 18]

Output:
25
-1

---

A simple Solution O(nlogn).

Implementation

• We should first sort the array in desc order which will take O(nlogn) time in worst case.
• Then we should start checking for a perfect square using Math.sqrt() method, Which takes O(logx).
• The first number we will get is the largest perfect square. If no perfect square is found then return -1.

let perfectSquare = (e) => {
//sort the array
 e.sort((a, b) => b - a);

//Check the perfect square for each element
 for(let i = 0; i < e.length; i++){
    if(e[i] > 0 && Math.sqrt(e[i]) % 1 === 0){
      return e[i]
    }
 } 
 return -1;
}

console.log(perfectSquare([17, 20, 27, 2, 3, 10]));
console.log(perfectSquare([16, 20, 25, 2, 3, 10]));

Output:
-1
25

Time Complexity: O(nlogn).
Space Complexity: O(n).

Time and Space complexity

• To sort the given array it would take O(nlogn). To find the sqaure root it will take O(logx) time and we have to check it for all the elements so it is O(n * logx) = O(nlogx). As we are executing them one after another O(nlogn + nlogx) = O(nlogn).
• If we are using Mergesort then space complexity is O(n) and if it is Quicksort then space complexity is O(1). We can use any of them but as it is worst case we are going with O(n).

---

Another Solution O(nlogx).

Implementation

• We should start checking for a perfect square using Math.sqrt() method for all the elements, Which takes O(nlogx).
• Then compare the maximum element between the current and the previous element and store the maximum.

let perfectSquare = (e) => {
let max = -1
//Check the perfect square for each element
 for(let i = 0; i < e.length; i++){
    if(e[i] > 0 && Math.sqrt(e[i]) % 1 === 0){
      max = Math.max(max, e[i]);
    }
 } 
 return max;
}

console.log(perfectSquare([17, 20, 27, 2, 3, 10]));
console.log(perfectSquare([16, 20, 25, 2, 3, 10]));

Output:
-1
25

Time Complexity: O(nlogx).
Space Complexity: O(1).

Time and Space complexity

• To find the sqaure root it will take O(logx) time and we have to check it for all the elements so it is O(n * logx) = O(nlogx).
• We are using constant space so the Space complexity is O(1).