Tasks Details
medium
Given a list of integers, return the maximum number of consecutive integers equal to each other after replacing at most K of them.
Task Score
100%
Correctness
100%
Performance
100%
There are N obligatory books in a school program syllabus. The program also defines the order in which books should be read. Each book comes from a specific age, such as the enlightenment or the baroque period. The more books in a row the students read from any given age, the more they learn about it. Moreover, if they read a book from a different age, they will get distracted.
Teachers are allowed to replace K books from the program with alternatives. They want students to learn as much as possible from a single age (although they have not picked a particular specific age). The amount learned can be measured by the number of consecutive books from the same age read by the students. What is the maximum number of consecutive books from the same age after replacing at most K of them?
Note that the new books (after replacement) can be any books from the chosen age. They do not need to be listed in the syllabus, so the teacher can always find K books from the same age.
Write a function:
class Solution { public int solution(int[] A, int K); }
that, given an array of integers A of length N, representing the ages of consecutive books from the school program syllabus, and an integer K, returns the maximum number of consecutive books from the same age after replacing at most K of them.
Examples:
1. Given A = [1, 1, 3, 4, 3, 3, 4] and K = 2, the function should return 5. Teachers can replace books from age 4 with books from age 3.
2. Given A = [4, 5, 5, 4, 2, 2, 4] and K = 0, the function should return 2. Teachers are not allowed to replace any books.
3. Given A = [1, 3, 3, 2] and K = 2, the function should return 4. Teachers can replace all the books from other ages with books from age 3.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- K is an integer within the range [0..N];
- each element of array A is an integer within the range [1..100,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 14 minutes
Notes
not defined yet
Code: 12:45:49 UTC,
java,
autosave
Code: 12:45:57 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193
// you can also use imports, for example:
package com.jay.test.codility;
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution3 {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>=n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, node.count, 0,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Code: 12:46:00 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>=n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, node.count, 0,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Analysis
Code: 12:59:00 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193
// you can also use imports, for example:
package com.jay.test.codility;
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution3 {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, startIndex+node.count, startIndex,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Code: 12:59:10 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
// you can also use imports, for example:
package com.jay.test.codility;
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution3 {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, startIndex+node.count, startIndex,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Code: 12:59:20 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, startIndex+node.count, startIndex,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Code: 12:59:21 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, startIndex+node.count, startIndex,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Analysis
Code: 12:59:29 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, startIndex+node.count, startIndex,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
}
Analysis
Code: 12:59:33 UTC,
java,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Solution {
Map<Integer,ArrayList<Node>> map= new HashMap<Integer,ArrayList<Node>>();
public int solution(int[] A, int K) {
long max=0;
if(A.length >100000 || K>100000)
return 0;
int count = 1;
if(A.length==1) return 1;
for (int i = 0; i < A.length; i++) {
if(A[i]>100000 || A[i+1]>100000) return 0;
if (A[i] == A[i + 1]) {
count++;
if(i==A.length-2)
{
i++;
addNode(A,new Node(0,i,count,0,0));
}
} else {
addNode(A,new Node(0,i,count,0,0));
count=1;
if(i>=A.length-2)
{
++i;
addNode(A,new Node(0,i,1,0,0));
}
}
}
for(ArrayList<Node> set:map.values())
{
Collections.sort(set,new Node());
//System.out.println(set);
int c=-1;
for(Node n:set)
{
// max=Math.max(max, n.continueCount);
c++;
if(n.rep<=K)
{
long remainRep=K-n.rep;
long canRep=A.length-1-n.end;
max=Math.max(max, n.count+Math.min(remainRep, canRep));
}else {
long remain=n.rep-K;
int p= p=getClosestK(set, c,new Node(0,0,0,remain,0));;
Node closest=set.get(p);
if(closest.rep<n.rep-K || closest.start>n.start) continue;
long c1=n.count-closest.count;
long rem=n.rep-closest.rep;
long addOn=Math.min(A.length-1-n.end+closest.start, K-rem);
assert(addOn>=0);
max=Math.max(max, c1+addOn+closest.continueCount);
}
max=Math.max(max, n.continueCount);
}
}
return (int) (max);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Solution3 [map=" + map + "]";
}
public void addNode(int A[],Node node)
{
ArrayList<Node> valueMap = map.get(A[(int)node.end]);
int totalReplace = 0;
long endIndex = node.end;
long startIndex = node.end + 1 - node.count;
if (valueMap != null && valueMap.size() > 0) {
Node lastNode = valueMap.get(valueMap.size()-1);
long rep= startIndex - lastNode.end - 1;
valueMap.add(new Node((int)startIndex,(int) node.end, lastNode.count + node.count+rep,
rep+lastNode.rep,node.count));
} else {
valueMap = new ArrayList();
valueMap.add(new Node((int)startIndex, (int)endIndex, startIndex+node.count, startIndex,node.count));
}
map.put(A[(int)endIndex], valueMap);
}
public static int getClosestK(ArrayList<Node> a,int c, Node x) {
int low = c;
int high = a.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
assert(mid < high);
long d1 = a.get(mid).rep - x.rep;
long d2 = a.get(mid+1).rep - x.rep;
if(d1==0) return mid;
if(d2==0) return mid+1;
if(d1>0 && d2>0) {
low =mid+1;
}else if(d2<0)
{
high=mid;
}
}
return low;
}
}
class Node implements Comparable<Node>,Comparator<Node>{
public Node()
{
}
public Node(long start,long end, long count,long rep,long continueCount )
{
this.start=start;
this.end=end;
this.count=count;
this.rep=rep;
this.continueCount=continueCount;
}
long start;
long end;
long count;
long continueCount;
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Node [start=" + start + ", end=" + end + ", count=" + count + ", rep=" + rep + "]";
}
long rep;
public int compareTo(Node o) {
// TODO Auto-generated method stub
return (int) (o.rep-this.rep);
}
public int compare(Node o1, Node o2) {
return (int)o1.compareTo(o2);
}
} Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.012 s
OK
2.
0.012 s
OK
3.
0.012 s
OK
1.
0.012 s
OK
2.
0.012 s
OK
3.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.012 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.012 s
OK
5.
0.012 s
OK
start_with_wrong
Tests where best interval does not start or does not end with book which should be chosen for optimal result.
Tests where best interval does not start or does not end with book which should be chosen for optimal result.
✔
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.008 s
OK
expand all
Correctness/performance tests
least_common_age_dominates
Tests where the overall least common age dominates the best interval.
Tests where the overall least common age dominates the best interval.
✔
OK
1.
0.032 s
OK
2.
0.020 s
OK
3.
0.164 s
OK
1.
0.256 s
OK
2.
0.256 s
OK
3.
0.576 s
OK
4.
0.568 s
OK
1.
0.804 s
OK
2.
0.244 s
OK
3.
0.920 s
OK
4.
0.912 s
OK
1.
1.576 s
OK
2.
0.276 s
OK
expand all
Performance tests
1.
0.012 s
OK
2.
0.012 s
OK
semilarge_random
Semi-large random tests to distinguish between O(n^2) and O(n*log(n)^2) solutions.
Semi-large random tests to distinguish between O(n^2) and O(n*log(n)^2) solutions.
✔
OK
1.
0.060 s
OK
2.
0.088 s
OK
3.
0.144 s
OK
1.
0.012 s
OK
1.
1.120 s
OK
2.
1.240 s
OK
3.
1.304 s
OK