Variations - ZCO15002

I’ve successfully solved this problem (CodeChef: Practical coding for everyone). But I wanted to solve this problem using yet another method. I thought that a merge sort type approach can work for this problem as we did in inversion count. So I partition the array in two halves. Find variation count for each half and the final sorted array when merging. Then return the result. But it provides me a WA judgment. Can somebody point out where am I being mistaken? Check method solve3(). Link: https://pastebin.com/7FW876kA.

@arita_roy, I have also thought the same as you. But I am also getting WA. Don’t know where am I wrong?

private static int merge(int[] arr, long k, int start, int mid, int end) {
int count = 0;
ArrayList left = new ArrayList<>();
ArrayList right = new ArrayList<>();
ArrayList result = new ArrayList<>();

		for (int i = start; i <= mid; i++) {
			left.add(arr[i]);
		}

		for (int i = mid + 1; i <= end; i++) {
			right.add(arr[i]);
		}

		int i = 0, j = 0;
		// 2,3 1
		while (i < left.size() && j < right.size()) {
			if (left.get(i) > right.get(j)) {
				result.add(right.get(j));
				if (Math.abs(left.get(i) - right.get(j)) >= k) {
					count += Math.abs(left.size() - i);
				}
				j++;
			} else {
				result.add(left.get(i));
				if (Math.abs(left.get(i) - right.get(j)) >= k) {
					count += Math.abs(right.size() - j);
				}
				i++;
			}
		}

		if (i != left.size()) {
			while (i != left.size()) {
				result.add(left.get(i));
				i++;
			}
		}
		if (j != right.size()) {
			while (j != right.size()) {
				result.add(right.get(j));
				j++;
			}
		}

		for (int j2 = 0; j2 < result.size(); j2++) {
			arr[j2 + start] = result.get(j2);
		}

		return count;
	}

I don’t know about your logic. But if someone finds wrong in this. Please comment.