Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

Filter by
Sorted by
Tagged with
1
vote
3answers
812 views

Reverse a sentence in Java

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word. Implement a function ...
4
votes
2answers
983 views

Next palindromic number

I wrote a function that takes a number and finds the next palindromic number. Time complexity is currently O(n2), which is really bad. How could one make this function more efficient? ...
-1
votes
1answer
85 views

For every integer in an array, find the nearest greater integer both before and after it

The given code gives correct output but exceeds the time limit and I have no idea how to optimize it. I know it is of \$O(n^2)\$ complexity but I am not able to get anywhere near to optimizing it. ...
0
votes
1answer
40 views
4
votes
5answers
1k views

Award Budget Cuts implementation in Java

PRAMP Award Budget Cuts The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee ...
4
votes
2answers
108 views

Compare Strings

You have been given two strings, A and B (of length N each) and Q queries. The strings contain only 0s and/or 1s. For every query, you are given an index i. You have to update the value at ...
2
votes
2answers
2k views

Program to shorten URL and decode it back to get original URL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL. Design the encode and ...
2
votes
1answer
552 views

Max Increase to Keep City Skyline in Java

In a 2-dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can ...
0
votes
2answers
485 views

Pancake sort inteview using java

Given an array of integers arr: Write a function flip(arr, k) that reverses the order of the first k elements in the array <...
8
votes
1answer
175 views

Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
1
vote
1answer
60 views

Algorithmic complexity of this algorithm to find all ordered permutations of length X

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars. For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
3
votes
0answers
510 views

Finding the majority element in a sequence of integers in \$O(n \log n)\$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in \$ O(n \log n)\$. The majority element is defined as the ...
5
votes
2answers
791 views

Merge non overlapping intervals

Merge Intervals Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their ...
6
votes
0answers
578 views

Intersection of two lists in Python

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],...
2
votes
4answers
1k views

Reverse the digits of an Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Return 0 if the result overflows and does not fit in a 32 bit signed integer This is my approach: <...
4
votes
1answer
199 views

“Tara's Beautiful Permutations” challenge

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank. Here is the challenge. Given an array of integers, where each number can appear at most ...
1
vote
1answer
377 views

Hackerrank “Breaking the Record” solution

I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken. Easiest way for me was to ...
3
votes
1answer
71 views

Compute leaderboard of competitive riders throughout a season

I have a table in my DB that contains Riders as rows and their points throughout the season as columns. Here are the columns: ...
4
votes
4answers
972 views

Power of two integers

Challenge: Given a positive integer which fits in a \$32\$ bit signed integer, find if it can be expressed as \$A^P\$ where \$P > 1\$ and \$A > 0\$. A and P both should be integers. ...
2
votes
1answer
413 views

Return the optimal time slot

Implement a function meetingPlanner that given the availability, slotsA and slotsB, of two people and a meeting duration dur, returns the earliest time slot that works for both of them and is of ...
3
votes
3answers
2k views

Return the anti-diagonals

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: ...
3
votes
3answers
205 views

Finding the number of ways to partition {1,2, …, N} into p1 and p2 such that sum(p1) == sum(p2)

I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
2
votes
0answers
40 views

Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
4
votes
5answers
995 views

Find The Duplicates in two arrays

Find The Duplicates Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note ...
0
votes
2answers
331 views

Space complexity of the “add two binary strings” challenge

I was solving this problem of "adding two string binary numbers" and came up with the following algorithm. I am trying to analyze its time and space complexity. While I was satisfied with its time ...
4
votes
1answer
122 views

2D discrete motion planner

I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
-2
votes
1answer
77 views

Leet Code :: Merge Binary Tree :: Time Complexity [closed]

Problem Statement: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into ...
4
votes
3answers
532 views

Detecting if two strings are anagrams

I am trying to write a function that detects if two strings are anagrams of one another; more specifically, I want the function to be linear in its time complexity (\$O(n)\$ where \$n\$ is the length ...
4
votes
2answers
528 views

Bottom-up singly linked list merge sort in C++

This is an implementation of a singly linked list merge sort I did on paper during a job interview recently, using a bottom-up approach. The requirement was simply "implement a merge sort for a ...
3
votes
1answer
134 views

Binary search for IOI problem: Cave

Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf Code ...
-1
votes
1answer
1k views

Sort multidimensional array based of the difference in the value

Sort multidimensional array based of the difference in the value, if value is same sort on first column. Constrains: No of rows can be any but fixed no of column ie 2. Example: <...
1
vote
2answers
117 views

Finding duplicates in arrays

I'm given two sorted arrays, arr1 and arr2. They can either be of the same length or arr2 ...
2
votes
1answer
310 views

Pig Latin Script and Runtime

Wrote a basic pig latin script in python where the input is a string and it outputs the pig latin equivalent. I was just wondering what the runtime of this code would be and if there was a way to make ...
1
vote
1answer
111 views

Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
4
votes
1answer
615 views

Genomic Range Query in Python

Recently, I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of the task. The solution in Python is based on prefix sum, and ...
2
votes
0answers
48 views

RTB, SSPs is True 2nd Price Auction Program

I've created this program that is intended to check if SSPs in RTB auctions run true second price auction. The program is running properly and returning the values as desired. I would like to get ...
3
votes
2answers
932 views

Most popular element with count in Array with Java

Here is the input array of int values Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 } Find the most repeated element with its count, example output; ...
4
votes
2answers
106 views

Adding input strings and finding occurrences of certain prefixes

A user inputs data using a keyword add word and when he wants to find words with particular prefix then he enters find keyword. ...
2
votes
1answer
241 views

Find all pairs in an array whose absolute difference equals x

I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute ...
4
votes
2answers
306 views

Design a O(1) data structure

How would I implement a data structure that supports the following in constant time? I got this question at a job interview, and the following is my solution. Please check my approach, or suggest a ...
5
votes
1answer
414 views

N queens variation recursion Python 3

I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) ...
1
vote
1answer
61 views

Given an array of integers, find and print its number of negative subarrays on a new line

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line. My code is taking \$\mathcal{O}(n^2)\$ time. How can I improve ...
1
vote
0answers
1k views

Find the length of minimum sub array with maximum degree in an array

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array ...
1
vote
2answers
498 views

Adding Combinations of Numbers in an Array

Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops? Take an array of integers and return a list of sums of every ...
2
votes
2answers
972 views

Python PEMDAS calculator [closed]

The goal of this calculator is to evaluate an expression with PEMDAS in mind (no parenthesis yet, adding soon). Although the program works, I want to make it as efficient as possible with the approach ...
10
votes
4answers
1k views

Maximum consecutive subarray sum for a variable sliding window size

The Problem: Given an array of integers L find the largest sum of a consecutive subarray of size k or less. Constraints: ...
-5
votes
1answer
210 views

Category of sorting algorithm and complexity [closed]

Just for fun, I wrote a sorting algorithm. I did not compare this with existing sorting algorithms.Can someone tell me what class of sorting algorithm this is and it's complexity? The algorithm ...
-3
votes
1answer
2k views

Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
3
votes
1answer
3k views

Calculating the most profit from an array of stock prices

I'm a newbie learning how to code, and I am trying to find the most efficient way to calculate the most profit from an array of stock prices. For a given array,I have a list of stock prices over n ...
2
votes
1answer
2k views

Implementation of Prim's Algorithm to find minimum spanning tree

What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue. ...