Algorithmic Problems

LeetCode in R?…

This page consists of algorithmic problems implemented in R, for fun and an extra challenge. Nothing here is in scope for STAT 33B. If you think you’ve solved some fun problem successfully in R, please send it to me! I’d be happy to include it here for others to see.

If you’re looking for problems to solve, I’d recommend Codeforces or LeetCode. Unfortunately, neither has R support. For this, I’d recommend CodeChef.

Two Sum

To start, the most popular problem on LeetCode! Click here to read the problem.

two_sum <- function(nums, target) {
  # Your code here
}

Show Solution

two_sum <- function(nums, target) {
  num_indices <- new.env() # we use an environment as a hash map
  for (i in seq_along(nums)) {
    dif <- as.character(target - nums[i])
    dif_index <- num_indices[[dif]]
    if (!is.null(dif_index))
      return(c(i, dif_index))
    num_indices[[as.character(nums[i])]] <- i
  }
  -1
}

QAQ

This one from Codeforces has a strange problem statement, but it’s a good exercise in using prefix arrays. Click here to read the problem.

qaq <- function(string) {
  # Your code here
}

I’ve provided two solutions. The first uses for/if and is more typical of what you’d see in other languages (and may be easier for you to read). The second is a R’ified version that doesn’t use for/if, instead relying on vectorization and functional programming.

Show for/if Solution

qaq <- function(string) {
  # Form a prefix vector for the number of "Q"s at each index.
  q_count <- numeric(nchar(string))
  for (i in seq_along(q_count)) {
    is_q <- as.integer(substr(string, i, i) == "Q")
    q_count[i] <- ifelse(i > 1, q_count[i - 1] + is_q, is_q)
  }
  
  # For each "A" we can form <"Q"s before "A"> * <"Q"s after "A"> "QAQ"s. We 
  # obtain this value for each "A" and sum them.  
  count <- 0
  for (i in seq_along(q_count)) {
    if (substr(string, i, i) == "A") {
      q_before <- q_count[i]
      q_after <- tail(q_count, 1) - q_count[i]
      count <- count + q_before * q_after
    }
  }
  count
}

Show R’ified Solution

qaq <- function(string) {
  # We'll be using these packages.
  require(magrittr); require(purrr)
  
  # Obtain the individual characters in `string`.
  characters <- strsplit(string, "")[[1]]
  
  # Form a prefix vector for the number of "Q"s at each index.
  q_count <- characters |>
    equals("Q") |>
    as.numeric() |>
    accumulate(`+`)
  
  # For each "A" we can form <"Q"s before "A"> * <"Q"s after "A"> "QAQ"s. We 
  # obtain this value for each "A" and sum them.
  characters |>
    equals("A") |>
    multiply_by(q_count) |>
    multiply_by(tail(q_count, 1) - q_count) |>
    sum()
}

Follow up: Can you do it without the prefix array while still iterating through string at most twice?

This page is in progress. Contributions are welcome.