Squares of a Sorted Array

🏠 ⬅️ ➡️

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer :: nums(n) = [-4, -1, 0, 3, 10]
    integer :: i, j
    integer :: squares(n)

    do i = 1, n
        squares(i) = nums(i) * nums(i)
    end do

    call sort_array(squares)

    write (*, '(A)') 'Squares:'
    do i = 1, n
        write (*, '(I0)', advance='no') squares(i)
    end do
    write (*, *)

contains

    subroutine sort_array(arr)
        implicit none
        integer, intent(inout) :: arr(:)
        integer :: temp
        integer :: i, j

        do i = 1, size(arr)-1
            do j = i+1, size(arr)
                if (arr(j) < arr(i)) then
                    temp = arr(j)
                    arr(j) = arr(i)
                    arr(i) = temp
                end if
            end do
        end do
    end subroutine sort_array

end program main
✅ Compiled
❌ Executed
❌ Correct 
! This script solves the problem of finding the squares of a sorted array of integers.

! Input:
!   nums: an integer array sorted in non-decreasing order

! Output:
!   an array of the squares of each number sorted in non-decreasing order

! Example 1:
!   Input: nums = [-4, -1, 0, 3, 10]
!   Output: [0, 1, 9, 16, 100]

! Example 2:
!   Input: nums = [-7, -3, 2, 3, 11]
!   Output: [4, 9, 9, 49, 121]

! Constraints:
!   1 <= nums.length <= 104
!   -104 <= nums[i] <= 104
!   nums is sorted in non-decreasing order.

! Follow up:
!   Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

! Declare variables
integer :: i, j, n, num, square
integer, dimension(:), allocatable :: nums, squares

! Read input
read (*,*) n
allocate(nums(n))
read (*,*) nums

! Initialize output array
allocate(squares(n))

! Loop through input array and calculate squares
do i = 1, n
    num = nums(i)
    square = num * num
    squares(i) = square
end do

! Sort output array
call sort(squares)

! Print output
do i = 1, n
    write (*,*) squares(i)
end do

contains

! Sorting subroutine
subroutine sort(arr)
    integer, dimension(:), intent(inout) :: arr
    integer :: i, j, temp

    do i = 1, size(arr) - 1
        do j = i + 1, size(arr)
            if (arr(i) > arr(j)) then
                temp = arr(i)
                arr(i) = arr(j)
                arr(j) = temp
            end if
        end do
    end do
end subroutine sort

end program
🌐 Data from online sources 
def distinctSubseqII(s):
    mod = 10**9 + 7
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    last = [-1] * 26

    for i in range(1, n + 1):
        dp[i] = (dp[i - 1] * 2) % mod
        if last[ord(s[i - 1]) - ord('a')] != -1:
            dp[i] = (dp[i] - dp[last[ord(s[i - 1]) - ord('a')]] + mod) % mod
        last[ord(s[i - 1]) - ord('a')] = i - 1

    dp[n] = (dp[n] - 1 + mod) % mod
    return dp[n]
  1. Initialize a dynamic programming array dp with length n+1 to store the number of distinct subsequences.
  2. Initialize an array last, with length 26, to store the last occurrences of each letter 'a'-'z'.
  3. Iterate through the string using the index i ranging from 1 to n.
  4. Calculate the number of distinct subsequences of length i by doubling the number of distinct subsequences of length i-1.
  5. If the last occurrence of the current letter is not -1, subtract the number of distinct subsequences at the index of the last occurrence from the current dp[i] value.
  6. Update the last occurrence array index of the current letter in the string.
  7. Subtract 1 from the number of subsequences of length n (removes the empty subsequence) and return the result modulo 1e9+7.
🌐 Data from online sources 
#include <iostream>
#include <string>

int distinctSubseqII(std::string s) {
    int mod = 1e9 + 7;
    int n = s.size();
    std::vector<int> dp(n + 1);
    dp[0] = 1;
    std::vector<int> last(26, -1); 

    for (int i = 1; i <= n; ++i) {
        dp[i] = (dp[i - 1] * 2) % mod;
        if (last[s[i - 1] - 'a'] != -1) {
            dp[i] = (dp[i] - dp[last[s[i - 1] - 'a']] + mod) % mod;
        }
        last[s[i - 1] - 'a'] = i - 1;
    }

    dp[n] = (dp[n] - 1 + mod) % mod;
    return dp[n];
}
  1. Initialize a dynamic programming array dp with length n+1 to store the number of distinct subsequences.
  2. Initialize an array last, with length 26, to store the last occurrences of each letter 'a'-'z'.
  3. Iterate through the string using the index i ranging from 1 to n.
  4. Calculate the number of distinct subsequences of length i by doubling the number of distinct subsequences of length i-1.
  5. If the last occurrence of the current letter is not -1, subtract the number of distinct subsequences at the index of the last occurrence from the current dp[i] value.
  6. Update the last occurrence array index of the current letter in the string.
  7. Subtract 1 from the number of subsequences of length n (removes the empty subsequence) and return the result modulo 1e9+7.