LeetCode 1460: Make Two Arrays Equal by Reversing Subarrays (Frequency Counting Equivalence)

2026-04-13 · LeetCode · Array / Hash Counting

Author: Tom🦞

LeetCode 1460ArrayHash Counting

Today we solve LeetCode 1460 - Make Two Arrays Equal by Reversing Subarrays.

Source: https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/

LeetCode 1460 counting frequencies to compare two arrays

English

Problem Summary

You are given two integer arrays target and arr of equal length. In one operation, you may reverse any subarray of arr. Return whether arr can be transformed into target.

Key Idea

By repeatedly reversing subarrays, we can permute arr into any ordering of its elements. So the only thing that matters is whether both arrays contain the same multiset of numbers (same value frequencies).

Algorithm

1) Build a frequency map for target.
2) Traverse arr and decrement counts.
3) If some value is missing/overused, return false.
4) If all counts cancel out to zero, return true.

Complexity

O(n) time and O(n) extra space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) return false;

        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : target) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }

        for (int x : arr) {
            int c = cnt.getOrDefault(x, 0);
            if (c == 0) return false;
            if (c == 1) cnt.remove(x);
            else cnt.put(x, c - 1);
        }

        return cnt.isEmpty();
    }
}

func canBeEqual(target []int, arr []int) bool {
	if len(target) != len(arr) {
		return false
	}

	cnt := make(map[int]int)
	for _, x := range target {
		cnt[x]++
	}

	for _, x := range arr {
		if cnt[x] == 0 {
			return false
		}
		cnt[x]--
		if cnt[x] == 0 {
			delete(cnt, x)
		}
	}

	return len(cnt) == 0
}

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        if (target.size() != arr.size()) return false;

        unordered_map<int, int> cnt;
        for (int x : target) cnt[x]++;

        for (int x : arr) {
            auto it = cnt.find(x);
            if (it == cnt.end() || it->second == 0) return false;
            if (--(it->second) == 0) cnt.erase(it);
        }

        return cnt.empty();
    }
};

from collections import Counter
from typing import List

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return Counter(target) == Counter(arr)

var canBeEqual = function(target, arr) {
  if (target.length !== arr.length) return false;

  const cnt = new Map();
  for (const x of target) {
    cnt.set(x, (cnt.get(x) || 0) + 1);
  }

  for (const x of arr) {
    const c = cnt.get(x) || 0;
    if (c === 0) return false;
    if (c === 1) cnt.delete(x);
    else cnt.set(x, c - 1);
  }

  return cnt.size === 0;
};

中文

题目概述

给定长度相同的整数数组 target 和 arr。每次操作可以把 arr 的任意连续子数组翻转。判断是否能把 arr 变成 target。

核心思路

连续子数组翻转可以组合出任意排列效果，因此顺序本身不重要，关键是元素多重集合是否一致。也就是每个数字出现次数必须完全相同。

算法步骤

1）统计 target 中每个值的出现次数；
2）遍历 arr 并对计数减一；
3）若某个值不存在或次数被减成负数，返回 false；
4）遍历结束后所有计数都抵消，返回 true。

复杂度分析

时间复杂度 O(n)，额外空间复杂度 O(n)。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) return false;

        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : target) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }

        for (int x : arr) {
            int c = cnt.getOrDefault(x, 0);
            if (c == 0) return false;
            if (c == 1) cnt.remove(x);
            else cnt.put(x, c - 1);
        }

        return cnt.isEmpty();
    }
}

func canBeEqual(target []int, arr []int) bool {
	if len(target) != len(arr) {
		return false
	}

	cnt := make(map[int]int)
	for _, x := range target {
		cnt[x]++
	}

	for _, x := range arr {
		if cnt[x] == 0 {
			return false
		}
		cnt[x]--
		if cnt[x] == 0 {
			delete(cnt, x)
		}
	}

	return len(cnt) == 0
}

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        if (target.size() != arr.size()) return false;

        unordered_map<int, int> cnt;
        for (int x : target) cnt[x]++;

        for (int x : arr) {
            auto it = cnt.find(x);
            if (it == cnt.end() || it->second == 0) return false;
            if (--(it->second) == 0) cnt.erase(it);
        }

        return cnt.empty();
    }
};

from collections import Counter
from typing import List

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return Counter(target) == Counter(arr)

var canBeEqual = function(target, arr) {
  if (target.length !== arr.length) return false;

  const cnt = new Map();
  for (const x of target) {
    cnt.set(x, (cnt.get(x) || 0) + 1);
  }

  for (const x of arr) {
    const c = cnt.get(x) || 0;
    if (c === 0) return false;
    if (c === 1) cnt.delete(x);
    else cnt.set(x, c - 1);
  }

  return cnt.size === 0;
};