Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Split Array by Prime Indices solution and explanation

MediumArrayMathNumber Theory4 min read49.3% acceptanceUpdated 24 Mar 2026
Practise Split Array by Prime Indices
11:28
Split Array by Prime Indices | Biweekly Contest 161 | Q1 | Leetcode 3618ExpertFunda · 11:28 · 270 viewsWatch on YouTube
9 more videos on this problem
  1. Split Array by Prime Indices | Biweekly Contest 161 | Q1 | Leetcode 3618ExpertFunda · 11:28 · 270 views
  2. 3618. Split Array by Prime Indices (Leetcode Medium)Programming Live with Larry · 4:35 · 234 views
  3. Biweekly Contest 161 | Leetcode 3618 - Split Array by Prime IndicesSamrat Bhardwaj · 5:18 · 110 views
  4. 3618. Split Array by Prime Indices | Prime NumberTech Courses · 4:01 · 95 views
  5. LeetCode 3618. Split Array by Prime Indices | Sieve of Eratosthenes | Prime Number | MediumLeet's Code · 8:36 · 88 views
  6. Split Array by Prime Indices | TCS NQT 2025 DSA Preparation | Leetcode 3618Algo Strive · 8:47 · 64 views
  7. 🔴 Biweekly Contest 161 | Split Array by Prime Indices | Every Question | Live Explanation and codingErDelhiBoy · 40:06 · 51 views
  8. 3618. Split Array by Prime Indices | Leetcode Bi-weekly Contest 161 | Array | PrimeBreak and Build · 11:15 · 49 views
  9. Split Array by Prime Indices | LeetCode 3618 | Number TheorycodeTips · 3:49 · 30 views
  10. Split Array by Prime Indices | Leetcode 3618 Explained with Code | Arrays Interview Question |ErDelhiBoy · 13:41 · 24 views

The problem

You are given an integer array nums.

Split nums into two arrays A and B using the following rule:

  • Elements at prime indices in nums must go into array A.
  • All other elements must go into array B.

Return the absolute difference between the sums of the two arrays: |sum(A) - sum(B)|.

Note: An empty array has a sum of 0.

Example 1:

Input: nums = [2,3,4]

Output: 1

Explanation:

  • The only prime index in the array is 2, so nums[2] = 4 is placed in array A.
  • The remaining elements, nums[0] = 2 and nums[1] = 3 are placed in array B.
  • sum(A) = 4, sum(B) = 2 + 3 = 5.
  • The absolute difference is |4 - 5| = 1.

Example 2:

Input: nums = [-1,5,7,0]

Output: 3

Explanation:

  • The prime indices in the array are 2 and 3, so nums[2] = 7 and nums[3] = 0 are placed in array A.
  • The remaining elements, nums[0] = -1 and nums[1] = 5 are placed in array B.
  • sum(A) = 7 + 0 = 7, sum(B) = -1 + 5 = 4.
  • The absolute difference is |7 - 4| = 3.

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Approach overview

Problem Overview: You are given an array and need to split or process its elements based on whether their indices are prime numbers. The core task is identifying prime indices efficiently and then simulating the required split or aggregation using those indices.

Approach 1: Naive Prime Check + Simulation (O(n * sqrt(n)) time, O(1) space)

The straightforward approach checks whether each index is prime by testing divisibility from 2 to sqrt(i). For every array index, run the prime check and then place or process the element accordingly. This method works for small inputs but becomes inefficient because each index requires a separate primality test. The algorithm repeatedly performs expensive checks even though many results could be reused.

Approach 2: Sieve of Eratosthenes + Simulation (O(n log log n) time, O(n) space)

The efficient solution precomputes all prime indices up to n - 1 using the Sieve of Eratosthenes. Create a boolean array where each position indicates whether the index is prime. Start by marking multiples of each prime number as non‑prime, which builds the complete prime table in O(n log log n) time. After building the sieve, iterate through the array once and check the precomputed prime flag for each index.

If the index is prime, process the element in the "prime index" group; otherwise place it in the "non‑prime index" group. The simulation step is linear and consists of simple array iteration and conditional checks. Because primality is already computed, each lookup is O(1), making the total runtime dominated by the sieve preprocessing.

This pattern frequently appears in problems combining array traversal with math utilities. Precomputing primes with a sieve is a standard optimization in number theory tasks where repeated prime checks are required.

Recommended for interviews: The Sieve of Eratosthenes + simulation approach is the expected solution. Interviewers want to see that you avoid repeated primality checks and instead precompute primes efficiently. Mentioning the naive method shows you understand the baseline, but using the sieve demonstrates stronger algorithmic optimization and familiarity with number‑theory preprocessing techniques.

Solution

We can use the Sieve of Eratosthenes to preprocess all prime numbers in the range [0, 10^5]. Then we iterate through the array nums. For nums[i], if i is a prime number, we add nums[i] to the answer; otherwise, we add -nums[i] to the answer. Finally, we return the absolute value of the answer.

Ignoring the preprocessing time and space, the time complexity is O(n), where n is the length of the array nums, and the space complexity is O(1).

m = 10**5 + 10
primes = [True] * m
primes[0] = primes[1] = False
for i in range(2, m):
    if primes[i]:
        for j in range(i + i, m, i):
            primes[j] = False


class Solution:
    def splitArray(self, nums: List[int]) -> int:
        return abs(sum(x if primes[i] else -x for i, x in enumerate(nums)))
class Solution {
    private static final int M = 100000 + 10;
    private static boolean[] primes = new boolean[M];

    static {
        for (int i = 0; i < M; i++) {
            primes[i] = true;
        }
        primes[0] = primes[1] = false;

        for (int i = 2; i < M; i++) {
            if (primes[i]) {
                for (int j = i + i; j < M; j += i) {
                    primes[j] = false;
                }
            }
        }
    }

    public long splitArray(int[] nums) {
        long ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            ans += primes[i] ? nums[i] : -nums[i];
        }
        return Math.abs(ans);
    }
}
const int M = 1e5 + 10;
bool primes[M];
auto init = [] {
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    for (int i = 2; i < M; ++i) {
        if (primes[i]) {
            for (int j = i + i; j < M; j += i) {
                primes[j] = false;
            }
        }
    }
    return 0;
}();

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        long long ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            ans += primes[i] ? nums[i] : -nums[i];
        }
        return abs(ans);
    }
};
const M = 100000 + 10;
const primes: boolean[] = Array(M).fill(true);

const init = (() => {
    primes[0] = primes[1] = false;

    for (let i = 2; i < M; i++) {
        if (primes[i]) {
            for (let j = i + i; j < M; j += i) {
                primes[j] = false;
            }
        }
    }
})();

function splitArray(nums: number[]): number {
    let ans = 0;
    for (let i = 0; i < nums.length; i++) {
        ans += primes[i] ? nums[i] : -nums[i];
    }
    return Math.abs(ans);
}
const M = 100000 + 10

var primes [M]bool

func init() {
	for i := 0; i < M; i++ {
		primes[i] = true
	}
	primes[0], primes[1] = false, false

	for i := 2; i < M; i++ {
		if primes[i] {
			for j := i + i; j < M; j += i {
				primes[j] = false
			}
		}
	}
}

func splitArray(nums []int) (ans int64) {
	for i, num := range nums {
		if primes[i] {
			ans += int64(num)
		} else {
			ans -= int64(num)
		}
	}
	return max(ans, -ans)
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Naive Prime Check + SimulationO(n * sqrt(n))O(1)When constraints are small or when demonstrating baseline logic before optimization
Sieve of Eratosthenes + SimulationO(n log log n)O(n)General case for large arrays where many prime index checks are required

Frequently asked questions

Is Split Array by Prime Indices easy or hard?

Split Array by Prime Indices is generally considered a medium‑difficulty problem. The array iteration itself is straightforward, but recognizing that repeated prime checks should be replaced with a sieve optimization is the key insight.

Split Array by Prime Indices Python/Java solution

The typical implementation first constructs a sieve array up to n−1, marking prime indices. Then a simple loop iterates through the array and processes elements depending on whether the index is prime. The same logic works across Python, Java, C++, Go, and TypeScript.

How to solve Split Array by Prime Indices in O(n)?

After precomputing prime indices using the sieve, the actual processing step runs in O(n). Iterate through the array once and check a boolean prime table to decide whether the current index belongs to the prime group or the non‑prime group. Each lookup is constant time.

What is the best approach for Split Array by Prime Indices?

The most efficient approach uses the Sieve of Eratosthenes to precompute all prime indices up to the array length. After building the sieve in O(n log log n) time, iterate through the array once and process elements based on whether their index is marked prime. This avoids repeated primality checks and keeps the simulation step linear.

Is Split Array by Prime Indices asked at Google/Amazon/Meta?

Problems involving prime preprocessing and array traversal appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often require identifying prime indices, using sieve techniques, or combining number theory with efficient array processing.

What data structure is used in Split Array by Prime Indices?

The core structure is a boolean array (or vector) used by the Sieve of Eratosthenes to mark prime numbers. The input array is then traversed while referencing this table to determine whether each index is prime.

What is the time complexity of Split Array by Prime Indices?

Using the optimal approach, the time complexity is O(n log log n) due to the Sieve of Eratosthenes preprocessing. The final array traversal is O(n). Space complexity is O(n) for storing the prime flags.

Comments

Now write it yourselfClose this page and solve Split Array by Prime Indices in the editor, without looking.
Practise Split Array by Prime Indices