Question

How to find the shortest identical consecutive subarray in an array with Java

Answer 1

import java.util.List; 
import java.util.Vector; 
import java.util.Arrays; 
import java.util.Collections; 

public class ShortestRunProgram {

    // ------------------------------------------------------------
    // 1. ARRAY VERSION
    // ------------------------------------------------------------
    public static int[] shortest_identical_consecutive_subarray(int[] arr) {
        if (arr.length == 0) return new int[0];

        int bestStart = 0;
        int bestLen = arr.length;

        int currentStart = 0;
        int currentLen = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                currentLen++;
            } else {
                if (currentLen < bestLen) {
                    bestLen = currentLen;
                    bestStart = currentStart;
                }
                currentStart = i;
                currentLen = 1;
            }
        }

        if (currentLen < bestLen) {
            bestLen = currentLen;
            bestStart = currentStart;
        }

        int[] result = new int[bestLen];
        System.arraycopy(arr, bestStart, result, 0, bestLen);
        
        return result;
    }

    // ------------------------------------------------------------
    // 2. VECTOR VERSION
    // ------------------------------------------------------------
    public static Vector<Integer> shortest_identical_consecutive_subvector(Vector<Integer> vec) {
        if (vec.isEmpty()) return new Vector<>();

        int bestStart = 0;
        int bestLen = vec.size();

        int currentStart = 0;
        int currentLen = 1;

        for (int i = 1; i < vec.size(); i++) {
            if (vec.get(i).equals(vec.get(i - 1))) {
                currentLen++;
            } else {
                if (currentLen < bestLen) {
                    bestLen = currentLen;
                    bestStart = currentStart;
                }
                currentStart = i;
                currentLen = 1;
            }
        }

        if (currentLen < bestLen) {
            bestLen = currentLen;
            bestStart = currentStart;
        }

        Vector<Integer> result = new Vector<>();
        for (int i = bestStart; i < bestStart + bestLen; i++) {
            result.add(vec.get(i));
        }

        return result;
    }

    // ------------------------------------------------------------
    // 3. LIST VERSION
    // ------------------------------------------------------------
    public static List<Integer> shortest_identical_consecutive_sublst(List<Integer> lst) {
        if (lst.isEmpty()) return Collections.emptyList();

        int bestStart = 0;
        int bestLen = lst.size();

        int currentStart = 0;
        int currentLen = 1;

        for (int i = 1; i < lst.size(); i++) {
            if (lst.get(i).equals(lst.get(i - 1))) {
                currentLen++;
            } else {
                if (currentLen < bestLen) {
                    bestLen = currentLen;
                    bestStart = currentStart;
                }
                currentStart = i;
                currentLen = 1;
            }
        }

        if (currentLen < bestLen) {
            bestLen = currentLen;
            bestStart = currentStart;
        }

        return lst.subList(bestStart, bestStart + bestLen);
    }

    // ------------------------------------------------------------
    // MAIN PROGRAM
    // ------------------------------------------------------------
    public static void main(String[] args) {

        int[] arr = {3,3,3, 7,7,7,7,7, 2,2, 5,5,5,5, 9,9,9,9,9,9};
        Vector<Integer> vec = new Vector<>(Arrays.asList(3,3,3, 7,7,7,7,7, 2,2, 5,5,5,5, 9,9,9,9,9,9));
        List<Integer> lst = Arrays.asList(3,3,3, 7,7,7,7,7, 2,2, 5,5,5,5, 9,9,9,9,9,9);

        // ARRAY
        int[] resultArr = shortest_identical_consecutive_subarray(arr);
        System.out.print("Array result: ");
        for (int x : resultArr) System.out.print(x + " ");
        System.out.println();

        // VECTOR
        Vector<Integer> resultVec = shortest_identical_consecutive_subvector(vec);
        System.out.print("Vector result: ");
        for (int x : resultVec) System.out.print(x + " ");
        System.out.println();

        // LIST
        List<Integer> resultLst = shortest_identical_consecutive_sublst(lst);
        System.out.print("List result: ");
        for (int x : resultLst) System.out.print(x + " ");
        System.out.println();
    }
}


/*
run:

Array result: 2 2 
Vector result: 2 2 
List result: 2 2 

*/

 

70+ SQL courses for beginners and professionals