Detect Pattern of Length M Repeated K or More Times

🏠 ⬅️ ➡️

Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3 Output: true Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2 Output: true Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3 Output: false Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Constraints:

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100
  • 1 <= m <= 100
  • 2 <= k <= 100
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 7
    integer, parameter :: m = 1
    integer, parameter :: k = 3
    integer, dimension(n) :: arr = (/ 1, 2, 4, 4, 4, 4, 3 /)
    logical :: result

    result = repeatedPattern(arr, m, k)
    if (result) then
        print *, "True"
    else
        print *, "False"
    end if

contains

    function repeatedPattern(arr, m, k) result(repeated)
        implicit none
        integer, intent(in) :: arr(:), m, k
        logical :: repeated
        integer :: i, j, count

        repeated = .false.
        do i = 1, size(arr)-m+1
            count = 0
            do j = i, i+m-1
                if (arr(j) == arr(i)) then
                    count = count + 1
                else
                    exit
                end if
            end do
            if (count >= k) then
                repeated = .true.
                exit
            end if
        end do
    end function repeatedPattern
end program main
❌ Compiled
❌ Executed
❌ Correct 
module repeated_pattern

implicit none

contains

function repeated_pattern(arr, m, k) result(output)

integer, intent(in) :: arr(:)
integer, intent(in) :: m
integer, intent(in) :: k
logical :: output

integer :: i, j, count

output = .false.

! loop through the array
do i = 1, size(arr) - m + 1

! check if the pattern is repeated k or more times
count = 0
do j = i, i + m - 1
if (arr(j) == arr(j + 1)) then
count = count + 1
else
exit
end if
end do

if (count >= k) then
output = .true.
exit
end if

end do

end function repeated_pattern

end module repeated_pattern

program test

use repeated_pattern

implicit none

integer, parameter :: arr = [1, 2, 4, 4, 4, 4]
integer, parameter :: m = 1
integer, parameter :: k = 3

write (*, *) repeated_pattern(arr, m, k)

end program test
🌐 Data from online sources 
def is_prefix_of_word(sentence: str, search_word: str) -> int:
    words = sentence.split(' ')
    for index, word in enumerate(words, start=1):
        if word.startswith(search_word):
            return index
    return -1

The algorithm for solving this problem consists of the following steps: 1. Split the given sentence into words based on the space delimiter. 2. Iterate over the list of words. 3. For each word, check if the searchWord is a prefix (using substring in C++, startsWith() in Java and JavaScript, and startswith() in Python). 4. If the searchWord is a prefix of the current word, return the current index (1-indexed). 5. If no word has searchWord as a prefix, return -1.

🌐 Data from online sources 
#include <string>
#include <sstream>

int isPrefixOfWord(std::string sentence, std::string searchWord) {
    std::istringstream iss(sentence);
    std::string word;
    int index = 1;
    while (iss >> word) {
        if (word.substr(0, searchWord.size()) == searchWord) {
            return index;
        }
        index++;
    }
    return -1;
}

The algorithm for solving this problem consists of the following steps: 1. Split the given sentence into words based on the space delimiter. 2. Iterate over the list of words. 3. For each word, check if the searchWord is a prefix (using substring in C++, startsWith() in Java and JavaScript, and startswith() in Python). 4. If the searchWord is a prefix of the current word, return the current index (1-indexed). 5. If no word has searchWord as a prefix, return -1.