2584. Split the Array to Make Coprime Products
Problem Description
In this problem, you're given an integer array nums
of length n
. The task is to find the smallest index i
(where 0 <= i <= n - 2
) such that splitting the array into two parts at index i
results in the product of the first i + 1
elements being coprime with the product of the remaining elements. Two numbers are coprime if their greatest common divisor (GCD) is equal to 1.
A split is considered valid if and only if the aforementioned condition of coprimality is satisfied. If no such index exists, the function should return -1
.
For example:
- With
nums = [4,7,8,15,3,5]
, a valid split occurs at indexi = 2
where the products are4*7*8 = 224
and15*3*5 = 225
, andgcd(224, 225) = 1
. - With
nums = [4,7,15,8,3,5]
, no valid split can be found, and the function should return-1
.
Intuition
The general approach to solving this problem is to iterate over the nums
array and at each index, we need to track the prime factors of the cumulative product of elements up to that index, as well as maintain a mapping of the last index at which each prime factor appears.
Here's a step-by-step breakdown on how we arrive at the solution:
-
Prime Factorization for each element: We iterate through the array and perform prime factorization for each element. This will help us in understanding the prime factors that make up each number in the array.
-
Tracking First and Last Occurrences: While doing the prime factorization, we maintain two data structures. One dictionary (
first
) to store the first occurrence of a prime factor and another list (last
) to note down the last occurrence of a prime factor that has been seen so far. If a prime factor appears again at a later index, we update thelast
list at the index of the first occurrence of this prime factor to the current index. -
Finding the Split Index: After completing the prime factorization and tracking, we iterate over the
last
list to find the smallest indexi
wherelast[i] < i
. This indicates that splitting the array at indexi
will have no common prime factors for the product of the firsti + 1
numbers and the product of the remaining numbers.
The index mx
is used to track the maximum index in last
that we have seen so far. If at any point mx < i
, we immediately return mx
as the answer - this is our split point. If we finish iterating over the list and don't find such an index, we return -1
, which means no valid split exists.
This solution is efficient since it avoids explicitly calculating the product of the subarrays, which could result in very large numbers, and it allows us to determine if the array can be split validly based on the presence of common prime factors between the two subarrays.
Learn more about Math patterns.
Solution Approach
The solution to this problem uses prime factorization and dictionary mapping to efficiently find the smallest valid split index.
Here's how the implementation works:
-
Prime Factorization: For each number
x
in the arraynums
, the algorithm finds its prime factors. Starting with the smallest prime number2
, the code iterates through potential factors increasingj
untilj
exceeds the square root ofx
. Ifx
is divisible byj
, it is repeatedly divided byj
until it is no longer divisible. In this way, each elementx
is broken down into its prime factors. -
Dictionary Mapping (first occurrence): The
first
dictionary keeps track of the first occurrence of each prime factor throughout the array. When a new prime factor is encountered, it's added to the dictionary with the current index as its value. -
List Tracking (last occurrence): Simultaneously, the list
last
is updated to track the last occurrence of a previously seen prime factor. If a prime factor that's already in thefirst
dictionary is found again, thelast
array at the index of the first occurrence of this factor (obtained from thefirst
dictionary) is updated to the current index. -
Finding the Valid Split: After populating the
first
andlast
data structures, the algorithm searches for the smallest indexi
at which the split can occur. To keep track of the split index, the algorithm uses the variablemx
to store the maximum value found so far inlast
. It iterates through thelast
array while updatingmx
to the current maximum index. If at any indexi
,mx
is found to be less thani
, it means that the common prime factors (if any) ofnums[0] to nums[i]
andnums[i+1] to nums[n-1]
are only found before indexi
. Hence,mx
is the valid smallest split index, and it is returned. -
Returning the Result: The iteration continues until the end of the list. If no valid split is found, the function returns
-1
.
The algorithm is efficient because it avoids the need to calculate the actual products of the subarrays, which can be very large and could lead to integer overflow. Instead, it relies on the presence of common prime factors to determine whether a split is valid. The use of a dictionary and list to track the first and last occurrence of prime factors allows for fast lookups and updates, resulting in an efficient solution.
The time complexity for this algorithm can be approximated as O(n * sqrt(m)), where n
is the length of the array, and m
is the maximum value in the array, since for each element we might need to iterate up to its square root to find all prime factors.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example where nums = [6, 5, 10]
:
- Initialize
first
dictionary andlast
array:
first = {} last = [-1, -1, -1] // -1 indicates that we haven't seen the prime factor yet
- Perform prime factorization on each number in
nums
and updatefirst
andlast
:
-
For
nums[0] = 6
, its prime factors are 2 and 3.first = {2: 0, 3: 0} last = [0, 0, -1] // We've seen 2 and 3 at index 0
-
For
nums[1] = 5
, its only prime factor is 5.first = {2: 0, 3: 0, 5: 1} last = [0, 0, -1] // No need to update as 5 is a new prime factor
-
For
nums[2] = 10
, its prime factors are 2 and 5. Factor 2 has been encountered before, so we update its last occurrence. Factor 5 has also been encountered before, but since its first and last occurrence is at the same index, there is no need to update.first = {2: 0, 3: 0, 5: 1} last = [2, 0, -1] // Update last occurrence of 2 to index 2 where it's seen again
- Search for the smallest index
i
as a valid split:
-
Iterate through
last
. We usemx
to store the maximum index found so far.- At
i = 0
,last[0] = 2
, somx = 2
. - At
i = 1
,last[1] = 0
, butmx
is still 2 (mx
remains the max oflast[0]
andlast[1]
).
- At
-
We encounter
i < mx
ati = 1
. This means that all prime factors seen in the firsti+1
elements (up to index 1) and all following elements (from index 2) are unique.
Thus, the valid split index found is i = 1
.
The algorithm concludes that the products of the first half 6 * 5
and the second half 10
do not have any common prime factors, so they are coprime. The smallest valid split index returned is 1
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findValidSplit(self, nums: List[int]) -> int:
5 # Dictionary to keep track of the first occurrence index of each prime factor
6 first_occurrence = {}
7 n = len(nums)
8
9 # List to keep track of the last occurrence index that can be reached
10 # from the first occurrence of each prime factor.
11 last_reachable = list(range(n))
12
13 # Iterate over the list of numbers to update first and last occurrence indices
14 for index, number in enumerate(nums):
15 factor = 2
16 # Factorize the number and update occurrences
17 while factor <= number // factor:
18 if number % factor == 0:
19 if factor in first_occurrence:
20 last_reachable[first_occurrence[factor]] = index
21 else:
22 first_occurrence[factor] = index
23 while number % factor == 0:
24 number //= factor
25 factor += 1
26
27 # Check for a prime number greater than 1 and update occurrences
28 if number > 1:
29 if number in first_occurrence:
30 last_reachable[first_occurrence[number]] = index
31 else:
32 first_occurrence[number] = index
33
34 # This will hold the maximum last occurrence index that we can reach
35 max_reach = last_reachable[0]
36
37 # Iterate over the last reachable list to find the valid split point
38 for index, max_index_for_current_factor in enumerate(last_reachable):
39 # If we find an index larger than the current maxValue, return the maximum
40 # last occurrence index that we have, as this is the valid split point
41 if max_reach < index:
42 return max_reach
43 max_reach = max(max_reach, max_index_for_current_factor)
44
45 # If we couldn't find a valid split point, return -1
46 return -1
47
1class Solution {
2 public int findValidSplit(int[] nums) {
3 // Map to track the first occurrence of each prime factor
4 Map<Integer, Integer> firstOccurrence = new HashMap<>();
5 int length = nums.length;
6 // Array to track the last occurrence where each prime factor can be found
7 int[] lastOccurrence = new int[length];
8
9 // Initialize lastOccurrence to the current index for each element
10 for (int i = 0; i < length; ++i) {
11 lastOccurrence[i] = i;
12 }
13
14 // Iterate over the array to update the first and last occurrences of each prime factor
15 for (int i = 0; i < length; ++i) {
16 int x = nums[i];
17 // Factorization by trial division
18 for (int j = 2; j <= x / j; ++j) {
19 if (x % j == 0) {
20 // If this factor has been seen before, update its last occurrence
21 if (firstOccurrence.containsKey(j)) {
22 lastOccurrence[firstOccurrence.get(j)] = i;
23 } else { // Otherwise, record its first occurrence
24 firstOccurrence.put(j, i);
25 }
26 // Remove this prime factor from x
27 while (x % j == 0) {
28 x /= j;
29 }
30 }
31 }
32 // Check for the last prime factor which can be larger than sqrt(x)
33 if (x > 1) {
34 if (firstOccurrence.containsKey(x)) {
35 lastOccurrence[firstOccurrence.get(x)] = i;
36 } else {
37 firstOccurrence.put(x, i);
38 }
39 }
40 }
41
42 // Variable to track the maximum last occurrence index found so far
43 int maxLastOccurrence = lastOccurrence[0];
44
45 // Iterate over the array to find a valid split
46 for (int i = 0; i < length; ++i) {
47 // If the current maximum last occurrence is before the current index, we found a valid split
48 if (maxLastOccurrence < i) {
49 return maxLastOccurrence;
50 }
51 // Update the maximum last occurrence
52 maxLastOccurrence = Math.max(maxLastOccurrence, lastOccurrence[i]);
53 }
54
55 // If no valid split is found, return -1
56 return -1;
57 }
58}
59
1#include <vector>
2#include <unordered_map>
3#include <numeric> // for iota function
4using namespace std;
5
6class Solution {
7public:
8 // Method to find a valid split in the vector nums
9 int findValidSplit(vector<int>& nums) {
10 // Map to keep track of first occurrences of prime factors
11 unordered_map<int, int> firstOccurrence;
12 int n = nums.size();
13
14 // Vector to keep track of the latest index where each prime appears
15 vector<int> lastOccurrence(n);
16 iota(lastOccurrence.begin(), lastOccurrence.end(), 0); // Initialize with indices
17
18 // Iterate over all elements to populate first and last occurrence information
19 for (int i = 0; i < n; ++i) {
20 int x = nums[i];
21 // Factorize the current number x using trial division
22 for (int j = 2; j <= x / j; ++j) {
23 if (x % j == 0) { // If j is a factor of x
24 // Update the occurrences for the prime factors
25 if (firstOccurrence.count(j)) {
26 lastOccurrence[firstOccurrence[j]] = i;
27 } else {
28 firstOccurrence[j] = i;
29 }
30 // Divide x by j as long as j is a factor
31 while (x % j == 0) {
32 x /= j;
33 }
34 }
35 }
36 // If there are any prime factors left, handle the remaining prime factor
37 if (x > 1) {
38 if (firstOccurrence.count(x)) {
39 lastOccurrence[firstOccurrence[x]] = i;
40 } else {
41 firstOccurrence[x] = i;
42 }
43 }
44 }
45
46 // Initialize the max last occurrence seen so far
47 int maxLastOccurrence = lastOccurrence[0];
48
49 // Iterate to determine the earliest valid split point
50 for (int i = 0; i < n; ++i) {
51 if (maxLastOccurrence < i) {
52 return maxLastOccurrence; // This is a valid split point
53 }
54 maxLastOccurrence = max(maxLastOccurrence, lastOccurrence[i]);
55 }
56
57 // If no split point found, return -1
58 return -1;
59 }
60};
61
1// Importing Map from the standard library to use as a hashmap
2import { max, min } from "lodash";
3
4// Function to find a valid split in the array nums
5function findValidSplit(nums: number[]): number {
6 // Map to keep track of the first occurrences of prime factors
7 let firstOccurrence: Map<number, number> = new Map();
8
9 // Array to keep track of the latest index where each prime appears
10 let lastOccurrence: number[] = Array.from(nums.keys());
11
12 // Iterate over all elements to populate first and last occurrence information
13 for (let i = 0; i < nums.length; ++i) {
14 let x = nums[i];
15
16 // Factorize the current number x using trial division
17 for (let j = 2; j <= Math.sqrt(x); ++j) {
18 if (x % j === 0) { // If j is a factor of x
19 // Update the occurrences for the prime factors
20 if (firstOccurrence.has(j)) {
21 lastOccurrence[firstOccurrence.get(j) as number] = i;
22 } else {
23 firstOccurrence.set(j, i);
24 }
25 // Divide x by j as long as j is a factor
26 while (x % j === 0) {
27 x /= j;
28 }
29 }
30 }
31
32 // If there are any prime factors left, handle the remaining prime factor
33 if (x > 1) {
34 if (firstOccurrence.has(x)) {
35 lastOccurrence[firstOccurrence.get(x) as number] = i;
36 } else {
37 firstOccurrence.set(x, i);
38 }
39 }
40 }
41
42 // Initialize the max last occurrence seen so far
43 let maxLastOccurrence: number = lastOccurrence[0];
44
45 // Iterate to determine the earliest valid split point
46 for (let i = 0; i < nums.length; ++i) {
47 maxLastOccurrence = max([maxLastOccurrence, lastOccurrence[i]]) as number;
48 if (maxLastOccurrence < i) {
49 return maxLastOccurrence; // This is a valid split point
50 }
51 }
52
53 // If no split point is found, return -1
54 return -1;
55}
56
Time and Space Complexity
The provided code block has two main parts to consider when analyzing the time complexity:
- The first loop where we iterate over
nums
and factorize each number, updatingfirst
andlast
based on the factors. - The second loop where we iterate over
last
to find the valid split.
For the first part, in the worst case, the factorization of each number can take O(sqrt(x))
time where x
is the value of the number being factorized. Since we are doing this for every number in nums
, and with n
being the size of nums
, the total time complexity for this part is O(n * sqrt(max(nums)))
.
The second part is a linear scan over the array last
, having a time complexity of O(n)
.
Therefore, the overall time complexity is O(n * sqrt(max(nums))) + O(n)
which simplifies to O(n * sqrt(max(nums)))
as sqrt(max(nums))
is the dominating factor.
The space complexity of the code is affected by the first
and last
data structures, which hold at most n
elements, giving us a space complexity of O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!